An efficient algorithm for multi-layer obstacle-avoiding rectilinear Steiner tree construction
Journal
Proceedings - Design Automation Conference
Pages
613-622
Date Issued
2012
Author(s)
Abstract
We consider the multi-layer obstacle-avoiding rectilinear Steiner minimal tree (OARSMT) problem and propose a reduction to transform a multi-layer instance into a 3D instance. Based on the reduction we apply computational geometry techniques to develop an efficient algorithm, utilizing existing OARSMT heuristics. Experimental results show that our algorithm provides a solution with excellent quality and has a significant speed-up compared to previously known results. © 2012 ACM.
Subjects
obstacle-avoidance; physical design; rectilinear steiner minimal tree (RSMT); routing
Other Subjects
Obstacle-avoiding; Physical design; Rectilinear steiner trees; routing; Steiner minimal tree; Algorithms; Collision avoidance; Computational geometry; Computer aided design; Heuristic methods; Forestry; Algorithms; Cad Cam; Computation; Experimentation; Geometry; Heuristic Methods; Optimization; Problem Solving
Type
conference paper