Title :
An efficient algorithm for multi-layer obstacle-avoiding rectilinear Steiner tree construction
Author :
Liu, Chih-Hung ; Chen, I-Che ; Lee, D.T.
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;
Conference_Titel :
Design Automation Conference (DAC), 2012 49th ACM/EDAC/IEEE
Conference_Location :
San Francisco, CA
Print_ISBN :
978-1-4503-1199-1
