Efficient steiner tree construction based on spanning graphs

Hai Zhou*

*Corresponding author for this work

Research output: Contribution to conferencePaperpeer-review

35 Scopus citations


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)
Number of pages6
StatePublished - 2003
Event2003 International Symposium on Physical Design - Monterey, CA, United States
Duration: Apr 6 2003Apr 9 2003


Other2003 International Symposium on Physical Design
Country/TerritoryUnited States
CityMonterey, CA


  • Minimal spanning tree
  • Routing
  • Steiner tree

ASJC Scopus subject areas

  • Electrical and Electronic Engineering


Dive into the research topics of 'Efficient steiner tree construction based on spanning graphs'. Together they form a unique fingerprint.

Cite this