A novel ultra-fast heuristic for VLSI CAD Steiner trees

Bharat Krishna, C. Y. Roger Chen, Naresh K. Sehgal

Research output: Contribution to journalConference Articlepeer-review


In all stages of VLSI chip design, routing estimation is required to account for the effect of interconnects. We propose a fast Steiner tree construction algorithm, which is 3-180 times faster for 10-300 point Steiner trees, and within 2.5% of the length of the Batched-1-Steiner tree. The proposed method can be used as a fast net length estimation tool in VLSI CAD applications, e.g. in the inner cycle of a floorplanning/placement engine.

Original languageEnglish (US)
Pages (from-to)192-197
Number of pages6
JournalProceedings of the IEEE Great Lakes Symposium on VLSI
StatePublished - 2003
EventProceedings of the 2003 ACM Great Lakes Symposium on VLSI - Washington, DC, United States
Duration: Apr 28 2003Apr 29 2003


  • Interconnect estimation
  • Routing
  • Steiner trees

ASJC Scopus subject areas

  • Electrical and Electronic Engineering


Dive into the research topics of 'A novel ultra-fast heuristic for VLSI CAD Steiner trees'. Together they form a unique fingerprint.

Cite this