Item Details

Closing the Gap: Near-Optimal Steiner Trees in Polynomial Time

Barrera, Tim; Griffith, Jeff; Robins, Gabriel; Zhang, Tongtong
Barrera, Tim
Griffith, Jeff
Robins, Gabriel
Zhang, Tongtong
We propose several efficient enhancements to the Iterated 1-Steiner (I1S) heuristic of Kahng and Robins [17] for the minimum rectilinear Steiner tree problem. For typical nets, our methods obtain average performance of less than 0.25% from optimal, and produce optimal solutions up to 90% of the time. We generalize IIS and its variants to three dimensions, as well as to the case where all the pins lie on is parallel planes, which arises in, e.g., multi-layer routing. Our algorithms are highly parallelizable, and extend to arbitrary weighted graphs, and thus, our methods are applicable in practical routing regimes. We prove that given a pointset in the Manhattan plane, the minimum spanning tree (MST) degree of any specific point can be made to be 4 or less; similarly, we show that in three dimensions, the MST degree of any specific point can be made 14 or less. Using a perturbative argument, these results have been recently extended to show that for every pointset in the Manhattan plane there exists an MST with maximum degree 4, and for three-dimensional Manhattan space the maximum MST degree is 14 [28]. Aside from having independent theoretical interest, these results help reduce the running times of our algorithms. Note: Abstract extracted from PDF file via OCR
University of Virginia, Department of Computer Science, 1993
Published Date
Libra Open Repository
Logo for In CopyrightIn Copyright


Access Online