Title :
Closing the gap: Near-optimal Steiner trees in polynomial time
Author :
Barrera, Tim ; Griffith, Jeff ; Robins, Gabriel ; Zhang, Tongtong
Author_Institution :
Dept. of Comput. Sci., Virginia Univ., Charlottesville, VA, USA
Abstract :
The authors enhance the Iterated 1-Steiner (I1S) MRST heuristic of A.B. Kahng, and G. Robins (1992). For typical nets, the methods obtain average performance of less than 0.25% from optimal, and produce optimal solutions in 90% of cases. The authors generalize I1S to higher dimensions, and prove that in 2-D and 3-D the MST degree of any point can be made ⩽4 and ⩽14, respectively. Aside from reducing the running times of the algorithms, these results are of independent theoretical interest
Keywords :
VLSI; circuit layout CAD; integrated circuit layout; network routing; trees (mathematics); 2-D; 3-D; VLSI; algorithms; circuit layout; iterated 1-Steiner heuristic; near-optimal Steiner trees; optimal solutions; polynomial time; running times; Approximation algorithms; Computer science; Cost function; Heuristic algorithms; Joining processes; Pins; Polynomials; Routing; Topology; Very large scale integration;
Conference_Titel :
ASIC Conference and Exhibit, 1993. Proceedings., Sixth Annual IEEE International
Conference_Location :
Rochester, NY
Print_ISBN :
0-7803-1375-5
DOI :
10.1109/ASIC.1993.410814
