An O(nlogn) edge-based algorithm for obstacle-avoiding rectilinear Steiner tree construction

Jieyi Long*, Hai Zhou, Seda Ogrenci Memik

*Corresponding author for this work

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

15 Scopus citations

Abstract

Obstacle-avoiding Steiner tree construction is a fundamental problem in VLSI physical design. In this paper, we provide a new approach for rectilinear Steiner tree construction in the presence of obstacles. We propose a novel algorithm, which generates sparse obstacle-avoiding spanning graphs efficiently. We design a fast algorithm for the minimum terminal spanning tree construction, which is the bottleneck step of several existing approaches in terms of running time. We adopt an edge-based heuristic, which enables us to perform both local and global refinement, leading to Steiner trees with small lengths. The time complexity of our algorithm is O(nlogn). Hence, our technique is the most efficient one to the best of our knowledge. Experimental results on various benchmarks show that our algorithm achieves 25.8 times speedup on average, while the average length of the resulting obstacle-avoiding rectilinear Steiner trees is only 1.58% larger than the best existing solution.

Original languageEnglish (US)
Title of host publicationISPD'08 - Proceedings of the 2008 ACM International Symposium on Physical Design
Pages126-133
Number of pages8
DOIs
StatePublished - May 16 2008
Event2008 ACM International Symposium on Physical Design, ISPD 2008 - Portland, OR, United States
Duration: Apr 13 2008Apr 16 2008

Publication series

NameProceedings of the International Symposium on Physical Design

Other

Other2008 ACM International Symposium on Physical Design, ISPD 2008
CountryUnited States
CityPortland, OR
Period4/13/084/16/08

Keywords

  • Minimum terminal spanning tree
  • Physical design
  • Routing
  • Spanning graph
  • Steiner tree

ASJC Scopus subject areas

  • Electrical and Electronic Engineering

Cite this