Advertisement
Published in:
2007 | OriginalPaper | Chapter
On the Minimum Corridor Connection Problem and Other Generalized Geometric Problems
Authors : Hans Bodlaender, Corinne Feremans, Alexander Grigoriev, Eelko Penninkx, René Sitters, Thomas Wolle
Published in: Approximation and Online Algorithms
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
In this paper we discuss the complexity and approximability of the minimum corridor connection problem where, given a rectilinear decomposition of a rectilinear polygon into “rooms”, one has to find the minimum length tree along the edges of the decomposition such that every room is incident to a vertex of the tree. We show that the problem is strongly NP-hard and give an subexponential time exact algorithm. For the special case of
k
-outerplanar graphs the running time becomes
O
(
n
3
). We develop a polynomial time approximation scheme for the case when all rooms are fat and have nearly the same size. When rooms are fat but are of varying size we give a polynomial time constant factor approximation algorithm.