A polynomial time approximation scheme for rectilinear Steiner minimum tree construction in the presence of obstacles

Jian Liu, Ying Zhao, Eugene Shragowitz, George Karypis

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

9 Scopus citations

Abstract

One problem in VLSI physical designs is to route multi-terminal nets in the presence of obstacles. This paper presents a polynomial time approximation scheme for construction of a rectilinear Steiner minimum tree in the presence of obstacles. Given any m rectangular obstacles, n nodes and ε>0, the scheme finds a (1 + ε) - approximation to the optimum solution in the time no(1/ε), providing an alternative of previous heuristics Remark: m is assumed to be a constant, otherwise when we solve the sub-problem in a brute force manner, we cannot declare that it can be solved in constant time.

Original languageEnglish (US)
Title of host publicationICECS 2002 - 9th IEEE International Conference on Electronics, Circuits and Systems
Pages781-784
Number of pages4
DOIs
StatePublished - Dec 1 2002
Event9th IEEE International Conference on Electronics, Circuits and Systems, ICECS 2002 - Dubrovnik, Croatia
Duration: Sep 15 2002Sep 18 2002

Publication series

NameProceedings of the IEEE International Conference on Electronics, Circuits, and Systems
Volume2

Other

Other9th IEEE International Conference on Electronics, Circuits and Systems, ICECS 2002
CountryCroatia
CityDubrovnik
Period9/15/029/18/02

Keywords

  • Approximation algorithm
  • Guillotine cut
  • PTAS
  • Rectilinear steiner minimum tree in presence of obstacles
  • VLSI routing

Fingerprint Dive into the research topics of 'A polynomial time approximation scheme for rectilinear Steiner minimum tree construction in the presence of obstacles'. Together they form a unique fingerprint.

Cite this