Title :
The polygonal contraction heuristic for rectilinear Steiner tree construction
Author :
Wang, Yin ; Hong, Xianlong ; Jing, Tong ; Yang, Yang ; Hu, Xiaodong ; Yan, Guiying
Author_Institution :
Dept. of Comput. Sci. & Technol., Tsinghua Univ., Beijing, China
Abstract :
Motivated by VLSI/ULSI routing applications, we present a heuristic for rectilinear Steiner minimal tree (RSMT) construction. We transform a rectilinear minimum spanning tree (RMST) into an RSMT by a novel method called polygonal contraction. Experimental results show that the heuristic matches or exceeds the solution quality of previously best known algorithms and runs much faster.
Keywords :
ULSI; VLSI; integrated circuit design; network routing; trees (mathematics); ULSI routing application; VLSI routing application; polygonal contraction; rectilinear Steiner minimal tree construction; rectilinear Steiner tree construction; rectilinear minimum spanning tree; Application software; Circuit topology; Computer science; Mathematics; Polynomials; Routing; Steiner trees; Surface-mount technology; Ultra large scale integration; Very large scale integration;
Conference_Titel :
Design Automation Conference, 2005. Proceedings of the ASP-DAC 2005. Asia and South Pacific
Print_ISBN :
0-7803-8736-8
DOI :
10.1109/ASPDAC.2005.1466119
