CLOSING THE GAP - NEAR-OPTIMAL STEINER TREES IN POLYNOMIAL-TIME

The minimum rectilinear Steiner tree (MRST) problem arises in global r outing and wiring estimation, as well as in many other areas. The MRST problem is known to be NP-hard, and the best performing MRST heuristi c to date is the Iterated 1-Steiner (I1S) method recently proposed by Kahng and Robins. In this paper, we develop a straightforward, efficie nt implementation of I1S, achieving a speedup factor of three orders o f magnitude over previous implementations. We also give a parallel imp lementation that achieves near-linear speedup on multiple processors. Several performance-improving enhancements enable us to obtain Steiner trees with average cost within 0.25% of optimal, and our methods prod uce optimal solutions in up to 90% of the cases for typical nets. We g eneralize IIS and its variants to three dimensions, as well as to the case where all the pins lie on k parallel planes, which arises in, e.g ., multilayer routing. Motivated by the goal of reducing the running t imes of our algorithms, we prove that any pointset in the Manhattan pl ane has a minimum spanning tree (MST) with maximum degree 4, and that in three-dimensional Manhattan space every pointset has an MST with ma ximum degree of 14 (the best previous upper bounds on the maximum MST degree in two and three dimensions are 6 and 26, respectively); these results are of independent theoretical interest and also settle an ope n problem in complexity theory.