The 1-Steiner tree problem in lambda-3 geometry plane

Author

Lin, Guo-Hui ; Thurber, Andrew P. ; Xue, Guoliang

Author_Institution

Dept. of Comput. Sci., Vermont Univ., Burlington, VT, USA

Volume

6

fYear

1999

fDate

36342

Firstpage

125

Abstract

In this paper, we extend the 1-Steiner idea of Georgakopoulos and Papadimitriou [1987] to the Steiner tree problem in lambda-3 geometry plane. Our extension to the lambda-3 geometry plane and that of Kahng and Robins [1992] to the rectilinear plane are similar in principle, but different in many nontrivial details. After presenting an efficient algorithm for solving the 1-Steiner tree problem, we apply the iterated 1-Steiner heuristic to compute approximations to the Steiner minimum tree problem in lambda-3 geometry plane. Computational results on standard benchmarks show that our algorithm compares favorably with previously published heuristics

Keywords

circuit layout CAD; computational geometry; minimisation; network routing; trees (mathematics); 1-Steiner tree problem; Steiner minimum tree problem; high-level description; iterated 1-Steiner heuristic; lambda-3 geometry plane; oriented Dirichlet diagrams; rectilinear plane; Algorithm design and analysis; Approximation algorithms; Computational geometry; Computer science; Intelligent networks; Printed circuits; Routing; Standards publication; Steiner trees; Wires;

fLanguage

English

Publisher

ieee

Conference_Titel

Circuits and Systems, 1999. ISCAS '99. Proceedings of the 1999 IEEE International Symposium on

Conference_Location

Orlando, FL

Print_ISBN

0-7803-5471-0

Type

conf

DOI

10.1109/ISCAS.1999.780111

Filename

780111