Efficient steiner tree construction based on spanning graphs

Hai Zhou*

*Corresponding author for this work

Research output: Contribution to conferencePaper

28 Scopus citations

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

Keywords

  • Minimal spanning tree
  • Routing
  • Steiner tree

ASJC Scopus subject areas

  • Electrical and Electronic Engineering

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

  • 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.