Approximation of Octilinear Steiner Trees Constrained by Hard and Soft Obstacles
MÃ¼llerHannemann, Matthias and Schulze, Anna
(2006)
Approximation of Octilinear Steiner Trees Constrained by Hard and Soft Obstacles.
Published In:
Algorithm theory  SWAT 2006 : 10th Scandinavian Workshop on Algorithm Theory, Riga, Latvia, July 6  8, 2006 ; proceedings, Lecture Notes in Computer Science. 4059 Springer 2006, pp. 242254.
Abstract
The novel octilinear routing paradigm (Xarchitecture) in VLSI design requires new approaches for the construction of Steiner trees. In this paper, we consider two versions of the shortest octilinear Steiner tree problem for a given point set K of terminals in the plane: (1) a version in the presence of hard octilinear obstacles, and (2) a version with rectangular soft obstacles. The interior of hard obstacles has to be avoided completely by the Steiner tree. In contrast, the Steiner tree is allowed to run over soft obstacles. But if the Steiner tree intersects some soft obstacle, then no connected component of the induced subtree may be longer than a given fixed length L. This kind of length restriction is motivated by its application in VLSI design where a large Steiner tree requires the insertion of buffers (or inverters) which must not be placed on top of obstacles. For both problem types, we provide reductions to the Steiner tree problem in graphs of polynomial size with the following approximation guarantees. Our main results are (1) a 2approximation of the octilinear Steiner tree problem in the presence of hard rectilinear or octilinear obstacles which can be computed in O(n log^2 n) time, where n denotes the number of obstacle vertices plus the number of terminals, (2) a (2 + epsilon)approximation of the octilinear Steiner tree problem in the presence of soft rectangular obstacles which runs in O(n^3) time, and (3) a (1.55 + epsilon)approximation of the octilinear Steiner tree problem in the presence of soft rectangular obstacles.
Editorial actions:  View Item (Login required) 

Item Type:  Proceedings article 

Citations:  7 (Google Scholar)  
Uncontrolled Keywords:  Approximation algorithms computational geometry octilinear Steiner trees obstacles VLSI design 
Subjects: 

Divisions:  Institute of Computer Science > Computer Science Department  Prof. Dr. Schrader Mathematical Institute > Prof. Dr. Faigle 
Related URLs: 
ZAIK Number:  zaik2007544 

Depositing User:  Anna Schulze 
Date Deposited:  22 Jun 2007 00:00 
Last Modified:  09 Nov 2011 15:45 
URI:  http://earchive.informatik.unikoeln.de/id/eprint/544 