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

30 Scopus citations

Abstract

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.
Pages348-351
Number of pages4
ISBN (Electronic)078037889X
DOIs
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
Volume1
ISSN (Print)1523-553X

Conference

Conference5th International Conference on ASIC, ASICON 2003
CountryChina
CityBeijing
Period10/21/0310/24/03

ASJC Scopus subject areas

  • Electronic, Optical and Magnetic Materials
  • Engineering(all)
  • Industrial and Manufacturing Engineering
  • Electrical and Electronic Engineering

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

Cite this