Efficient Steiner tree construction based on spanning graphs

Hai Zhou

doi:10.1109/TCAD.2004.826557

Efficient Steiner tree construction based on spanning graphs

Hai Zhou^*

^*Corresponding author for this work

Electrical and Computer Engineering

Research output: Contribution to journal › Article › peer-review

30 Scopus citations

Abstract

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.

Original language	English (US)
Pages (from-to)	704-710
Number of pages	7
Journal	IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Volume	23
Issue number	5
DOIs	https://doi.org/10.1109/TCAD.2004.826557
State	Published - May 2004

Keywords

Graph algorithms
Routing
Steiner tree

ASJC Scopus subject areas

Software
Computer Graphics and Computer-Aided Design
Electrical and Electronic Engineering

Access to Document

10.1109/TCAD.2004.826557

Cite this

@article{121b2142b1b747299adba67fe8962249,

title = "Efficient Steiner tree construction based on spanning graphs",

abstract = "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.",

keywords = "Graph algorithms, Routing, Steiner tree",

author = "Hai Zhou",

note = "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: haizhou@ece.nwu.edu). Digital Object Identifier 10.1109/TCAD.2004.826557",

year = "2004",

month = may,

doi = "10.1109/TCAD.2004.826557",

language = "English (US)",

volume = "23",

pages = "704--710",

journal = "IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems",

issn = "0278-0070",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

number = "5",

}

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: haizhou@ece.nwu.edu). 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 -

Efficient Steiner tree construction based on spanning graphs

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this