Rectilinear steiner minimal tree among obstacles

Yang Yang, Qi Zhu, Tong Jing, Xianlong Hong, Yin Wang

Research output: Chapter in Book/Report/Conference proceedingConference contribution

31 Scopus citations


Rectilinear Steiner Minimal Tree (RSMT) is one of the key problems in VLSI/ULSI physical design. RSMT construction among obstacles is often used as an accurate estimation for wire length and delay throughout the process of routing, even placement and floorplanning. This paper studies RSMT problem among obstacles and presents an O(mn) 2-step heuristic for multi-terminal tree construction, where HI is the number of obstacles and n is the number of terminals. Tltis heuristic has been implemented and tested on MCNC benchmarks. The experimental results are encouraging.

Original languageEnglish (US)
Title of host publicationASICON 2003 - 2003 5th International Conference on ASIC, Proceedings
EditorsTing-Ao Tang, Wenhong Li, Huihua Yu
PublisherInstitute of Electrical and Electronics Engineers Inc.
Number of pages4
ISBN (Electronic)078037889X
StatePublished - 2003
Externally publishedYes
Event5th International Conference on ASIC, ASICON 2003 - Beijing, China
Duration: Oct 21 2003Oct 24 2003

Publication series

NameIEEE International Symposium on Semiconductor Manufacturing Conference Proceedings
ISSN (Print)1523-553X


Conference5th International Conference on ASIC, ASICON 2003

ASJC Scopus subject areas

  • Electronic, Optical and Magnetic Materials
  • General Engineering
  • Industrial and Manufacturing Engineering
  • Electrical and Electronic Engineering


Dive into the research topics of 'Rectilinear steiner minimal tree among obstacles'. Together they form a unique fingerprint.

Cite this