Efficient 2-step heuristics for rectilinear Steiner minimal tree construction among obstacles

Yang Yang*, Tong Jing, Xianlong Hong, Qi Zhu, Yin Wang

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

Abstract

A primary tree is first constructed without considering obstacles. Intersections of the primary tree edges with obstacles are found out and relevant parts of the primary tree are reconnected to keep clear of obstacles while the total length of the tree being shortest. Moreover, a preprocessing and post-processing are added into the second step to tackle some special treatments and improve the solution quality. The heuristics can deal with multi-obstacle and obstacles of diversified shapes with O(mn) complexity, where m is the number of obstacles and n is the number of terminals. Experimental tests on MCNC benchmarks show that the algorithm can get good results on wire length, its average redundancy compared with minimal trees is 5.31% and the runtime for all cases is within 1 second.

Original languageEnglish (US)
Pages (from-to)223-229
Number of pages7
JournalJisuanji Fuzhu Sheji Yu Tuxingxue Xuebao/Journal of Computer-Aided Design and Computer Graphics
Volume17
Issue number2
StatePublished - Feb 2005

Keywords

  • Multi-terminal
  • Obstacles
  • Rectilinear Steiner minimal tree (RSMT)
  • Routing

ASJC Scopus subject areas

  • Software
  • Computer Graphics and Computer-Aided Design

Fingerprint

Dive into the research topics of 'Efficient 2-step heuristics for rectilinear Steiner minimal tree construction among obstacles'. Together they form a unique fingerprint.

Cite this