Hardness and Approximation of Octilinear Steiner Trees
MüllerHannemann, Matthias and Schulze, Anna
(2005)
Hardness and Approximation of Octilinear Steiner Trees.
Published In:
Algorithms and computation 16th International Symposium, ISAAC 2005, Sanya, Hainan, China, December 1921, 2005 ; proceedings, Lecture Notes in Computer Science. 3827 Springer 2005, pp. 256265.
Abstract
Given a point set K of terminals in the plane, the octilinear Steiner tree problem is to find a shortest tree that interconnects all terminals and edges run either in horizontal, vertical, or 45Â° diagonal direction. This problem is fundamental for the novel octilinear routing paradigm in VLSI design, the socalled Xarchitecture. As the related rectilinear and the Euclidian Steiner tree problem are wellknown to be NPhard, the same was widely believed for the octilinear Steiner tree problem but left open for quite some time. In this paper, we prove the NPcompleteness of the decision version of the octilinear Steiner tree problem. We also show how to reduce the octilinear Steiner tree problem to the Steiner tree problem in graphs of polynomial size with the following approximation guarantee. We construct a graph of size O(n^2/epsilon^2) which contains a (1+epsilon)approximation of a minimum octilinear Steiner tree for every epsilon > 0 and n = K. Hence, we can apply any kapproximation algorithm for the Steiner tree problem in graphs (the currently best known bound is k=1.55) and achieve an (k+epsilon) approximation bound for the octilinear Steiner tree problem. This approximation guarantee also holds for the more difficult case where the Steiner tree has to avoid blockages (obstacles bounded by octilinear polygons).
Editorial actions:  View Item (Login required) 

Item Type:  Proceedings article 

Citations:  3 (Google Scholar)  
Uncontrolled Keywords:  octilinear Steiner trees NPcompleteness VLSI design approximation algorithms blockages 
Subjects: 

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

Depositing User:  Anna Schulze 
Date Deposited:  22 Jun 2007 00:00 
Last Modified:  12 Aug 2011 13:36 
URI:  http://earchive.informatik.unikoeln.de/id/eprint/546 