The polygonal contraction heuristic for rectilinear Steiner tree construction

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.

REFERENCES

• 1: Yu Hu, Tong Jing, Xianlong Hong, Zhe Feng, Xiaodong Hu, and Guiying Yan. An efficient rectilinear steiner minimum tree algorithm based on ant colony optimization. In Proceedings of IEEE ICCCAS, pages 1276--1280, Chengdu, China, 2004.
• 2: Qi Zhu, Hai Zhou, Tong Jing, Xianlong Hong, and Yang Yang. Efficient octilinear steiner tree construction based on spanning graphs. In Proceedings of IEEE/ACM ASP-DAC, pages 687--690, Yokohama, Japan, 2004.
• 3: Yukun Cheng, Guiying Yan, and Tong Jing. The structural properties of hexagonal steiner minimum trees for terminals on the boundary of an equilateral triangle. In Proceedings of ISC&I, pages 61--65, Zhuhai, China, 2004.
• 4: Jingyu Xu , Xianlong Hong , Tong Jing , Yici Cai , Jun Gu, An efficient hierarchical timing-driven Steiner tree algorithm for global routing, Integration, the VLSI Journal, v.35 n.2, p.69-84, August 2003 [doi>10.1016/S0167-9260(03)00029-4]
• 5: H. Y. Bao, X. L. Hong, and Y. C. Cai. Timing-driven steiner tree algorithm based on sakurai model. Chinese Journal of Semiconductors, 20(1):41--46, 1999.
• 6: Yu Hu, Zhe Feng, Tong Jing, Xianlong Hong, Yang Yang, Ge Yu, Xiaodong Hu, and Guiying Yan. Forst: A 3-step heuristic for obstacle-avoiding rectilinear steiner minimal tree construction. In Proceedings of ISC&I, pages 1017--1021, Zhuhai, China, 2004.
• 7: Yang Yang, Qi Zhu, Tong Jing, Xianlong Hong, and Yin Wang. Rectilinear steiner minimal tree among obstacles. In Proceedings of IEEE ASICON, pages 348--351, Beijing, China, 2003.
• 8: M. R. Garey and D. S. Johnson. The rectilinear steiner problem is NP-Complete. SIAM Journal on Applied Mathematics, 32:826--834, 1977.
• 9: D. M. Warme, P. Winter, and M. Zacharisen. Geosteiner 3.1. Package.
• 10: S. Arora, Polynomial time approximation schemes for Euclidean TSP and other geometric problems, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.2, October 14-16, 1996
• 11: Jeff Griffith, Gabriel Robins, Jeffrey S. Salowe, and Tongtong Zhang. Closing the gap: Near-optimal steiner trees in polynomial time. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 13(11):1351--1365, November 1994.
• 12: M. Borah, R. M. Owens, and M. J. Irwin. An edge-based heuristic for steiner routing. IEEE Transactions on Computer Aided Design, 13(1563--1568), 1994.
• 13: Andrew B. Kahng , Ion I. Măndoiu , Alexander Z. Zelikovsky, Highly scalable algorithms for rectilinear and octilinear Steiner trees, Proceedings of the 2003 conference on Asia South Pacific design automation, January 21-24, 2003, Kitakyushu, Japan [doi>10.1145/1119772.1119955]
• 14: Hai Zhou, Efficient Steiner tree construction based on spanning graphs, Proceedings of the 2003 international symposium on Physical design, April 06-09, 2003, Monterey, CA, USA [doi>10.1145/640000.640034]
• 15: Andew Chi-Chih Yao. On constructing minimum spanning trees in k-dimensional spaces and related problems. SIAM Journal on Computing, 11(4):721--736, November 1982.
• 16: Leonidas J. Guibas and Jorge Stolfi. On computing all north-east nearest neighbors in the L1 metric. Information Processing Letters, 17, 1983.
• 17: Hai Zhou , Narendra Shenoy , William Nicholls, Efficient minimum spanning tree construction without Delaunay triangulation, Information Processing Letters, v.81 n.5, p.271-276, 2002 [doi>10.1016/S0020-0190(01)00232-0]
• 18: David Cheriton and Robert Endre Tarjan. Finding minimum spanning trees. SIAM Journal on Computing, 5(4):724--742, December 1976.
• 19: D. T. Lee and C. K. Wong. Voronoi diagrams in L1(L∞) metric with 2-dimensional storage applications. SIAM Journal of Computing, 9:200--211, 1980.
• 20: Gary M. Shute, Linda L. Deneen, and Clark D. Thomborson. An O(n log n) plane-sweep algorithm for L1 and L∞ delaunay triangulations. Algorithmica, 6:207--221, 1991.
• 21: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 22: A. B. Kahng and G. Robins. A new class of iterated steiner tree heuristics with good performance. IEEE trans. Computer-Aided Design, 11:893--902, 1992.