DocumentCode
565188
Title
An efficient algorithm for multi-layer obstacle-avoiding rectilinear Steiner tree construction
Author
Liu, Chih-Hung ; Chen, I-Che ; Lee, D.T.
fYear
2012
fDate
3-7 June 2012
Firstpage
613
Lastpage
622
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.
Keywords
computational geometry; integrated circuit design; trees (mathematics); 3D instance; computational geometry; integrated circuit design; multilayer instance; multilayer obstacle-avoiding rectilinear Steiner minimal tree problem; multilayer obstacle-avoiding rectilinear Steiner tree construction; Algorithm design and analysis; Approximation algorithms; Integrated circuits; Joining processes; Routing; Steiner trees; Transforms; Obstacle-Avoidance; Physical Design; Rectilinear Steiner Minimal Tree (RSMT); Routing;
fLanguage
English
Publisher
ieee
Conference_Titel
Design Automation Conference (DAC), 2012 49th ACM/EDAC/IEEE
Conference_Location
San Francisco, CA
ISSN
0738-100X
Print_ISBN
978-1-4503-1199-1
Type
conf
Filename
6241570
Link To Document