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 language | English (US) |
---|---|
Pages (from-to) | 223-229 |
Number of pages | 7 |
Journal | Jisuanji Fuzhu Sheji Yu Tuxingxue Xuebao/Journal of Computer-Aided Design and Computer Graphics |
Volume | 17 |
Issue number | 2 |
State | Published - Feb 2005 |
Keywords
- Multi-terminal
- Obstacles
- Rectilinear Steiner minimal tree (RSMT)
- Routing
ASJC Scopus subject areas
- Software
- Computer Graphics and Computer-Aided Design