TY - JOUR
T1 - Efficient Steiner tree construction based on spanning graphs
AU - Zhou, Hai
N1 - Funding Information:
Manuscript received June 10, 2003; revised August 18, 2003. This work was supported in part by the National Science Foundation under Grant CCR-0238484. This paper was recommended by Associate Editor J. Lillis. The author is with the Department of Electrical and Computer Engineering, Northwestern University, Evanston, IL 60208 USA (e-mail: [email protected]). Digital Object Identifier 10.1109/TCAD.2004.826557
PY - 2004/5
Y1 - 2004/5
N2 - The Steiner Minimal Tree (SMT) problem is a very important problem in very large scale integrated computer-aided design. Given n points on a plane, an SMT connects these points through some extra points (called Steiner points) to achieve a minimal total length. Even though there exist many heuristic algorithms for this problem, they have either poor performances or expensive running time. This paper records an implementation of an efficient SMT algorithm that has a worst case running time of O(n log n) and a performance close to that of the Iterated 1-Steiner algorithm. The algorithm efficiently combines Borah et al.'s edge substitute concept with Zhou et al.'s spanning graph. Extensive experimental studies are conducted to compare it with other programs.
AB - The Steiner Minimal Tree (SMT) problem is a very important problem in very large scale integrated computer-aided design. Given n points on a plane, an SMT connects these points through some extra points (called Steiner points) to achieve a minimal total length. Even though there exist many heuristic algorithms for this problem, they have either poor performances or expensive running time. This paper records an implementation of an efficient SMT algorithm that has a worst case running time of O(n log n) and a performance close to that of the Iterated 1-Steiner algorithm. The algorithm efficiently combines Borah et al.'s edge substitute concept with Zhou et al.'s spanning graph. Extensive experimental studies are conducted to compare it with other programs.
KW - Graph algorithms
KW - Routing
KW - Steiner tree
UR - http://www.scopus.com/inward/record.url?scp=2542477033&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=2542477033&partnerID=8YFLogxK
U2 - 10.1109/TCAD.2004.826557
DO - 10.1109/TCAD.2004.826557
M3 - Article
AN - SCOPUS:2542477033
SN - 0278-0070
VL - 23
SP - 704
EP - 710
JO - IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
JF - IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
IS - 5
ER -