Efficient steiner tree construction based on spanning graphs

Hai Zhou*

*Corresponding author for this work

Research output: Contribution to conferencePaper

26 Citations (Scopus)

Abstract

Steiner Minimal Tree (SMT) problem is a very important problem in VLSI CAD. Given n points on a plane, a Steiner minimal tree 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 times. This paper records an implementation of an efficient Steiner minimal tree algorithm that has a worst case running time of O(n log n) and a similar performance as 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 languageEnglish (US)
Pages152-157
Number of pages6
StatePublished - Jul 28 2003
Event2003 International Symposium on Physical Design - Monterey, CA, United States
Duration: Apr 6 2003Apr 9 2003

Other

Other2003 International Symposium on Physical Design
CountryUnited States
CityMonterey, CA
Period4/6/034/9/03

Fingerprint

Heuristic algorithms
Computer aided design

Keywords

  • Minimal spanning tree
  • Routing
  • Steiner tree

ASJC Scopus subject areas

  • Electrical and Electronic Engineering

Cite this

Zhou, H. (2003). Efficient steiner tree construction based on spanning graphs. 152-157. Paper presented at 2003 International Symposium on Physical Design, Monterey, CA, United States.
Zhou, Hai. / Efficient steiner tree construction based on spanning graphs. Paper presented at 2003 International Symposium on Physical Design, Monterey, CA, United States.6 p.
@conference{fef6c99906894d5f865835779f0eaed6,
title = "Efficient steiner tree construction based on spanning graphs",
abstract = "Steiner Minimal Tree (SMT) problem is a very important problem in VLSI CAD. Given n points on a plane, a Steiner minimal tree 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 times. This paper records an implementation of an efficient Steiner minimal tree algorithm that has a worst case running time of O(n log n) and a similar performance as 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 = "Minimal spanning tree, Routing, Steiner tree",
author = "Hai Zhou",
year = "2003",
month = "7",
day = "28",
language = "English (US)",
pages = "152--157",
note = "2003 International Symposium on Physical Design ; Conference date: 06-04-2003 Through 09-04-2003",

}

Zhou, H 2003, 'Efficient steiner tree construction based on spanning graphs' Paper presented at 2003 International Symposium on Physical Design, Monterey, CA, United States, 4/6/03 - 4/9/03, pp. 152-157.

Efficient steiner tree construction based on spanning graphs. / Zhou, Hai.

2003. 152-157 Paper presented at 2003 International Symposium on Physical Design, Monterey, CA, United States.

Research output: Contribution to conferencePaper

TY - CONF

T1 - Efficient steiner tree construction based on spanning graphs

AU - Zhou, Hai

PY - 2003/7/28

Y1 - 2003/7/28

N2 - Steiner Minimal Tree (SMT) problem is a very important problem in VLSI CAD. Given n points on a plane, a Steiner minimal tree 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 times. This paper records an implementation of an efficient Steiner minimal tree algorithm that has a worst case running time of O(n log n) and a similar performance as 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 - Steiner Minimal Tree (SMT) problem is a very important problem in VLSI CAD. Given n points on a plane, a Steiner minimal tree 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 times. This paper records an implementation of an efficient Steiner minimal tree algorithm that has a worst case running time of O(n log n) and a similar performance as 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 - Minimal spanning tree

KW - Routing

KW - Steiner tree

UR - http://www.scopus.com/inward/record.url?scp=0038040195&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0038040195&partnerID=8YFLogxK

M3 - Paper

SP - 152

EP - 157

ER -

Zhou H. Efficient steiner tree construction based on spanning graphs. 2003. Paper presented at 2003 International Symposium on Physical Design, Monterey, CA, United States.