Title :
New approximations for the rectilinear Steiner arborescence problem [VLSI layout]
Author :
Ramnath, Sarnath
Author_Institution :
Dept. of Comput. Sci., St. Cloud State Univ., MN, USA
fDate :
7/1/2003 12:00:00 AM
Abstract :
A new approach for approximating the minimum rectilinear Steiner arborescence is presented. The approach yields a simple two-approximation algorithm that runs in O(nlogn) time. Unlike earlier approaches, this can be naturally extended to deal with situations where we have isothetic rectilinear obstacles. This gives us the first O(nlogn) two-approximation algorithm for the rectilinear Steiner arborescence problem in the presence of obstacles.
Keywords :
VLSI; approximation theory; circuit layout CAD; computational complexity; integrated circuit layout; network routing; trees (mathematics); VLSI physical design; isothetic rectilinear obstacles; rectilinear Steiner arborescence problem; signal net routing; two-approximation algorithm; very large scale integration; Approximation algorithms; Clouds; Computer science; Dynamic programming; Joining processes; Linear programming; Routing; Signal design; Steiner trees; Very large scale integration;
Journal_Title :
Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on
DOI :
10.1109/TCAD.2003.814249
