On the minimum corridor connection problem and other generalized geometric problems |
| |
| Authors: | Hans L. Bodlaender, Corinne Feremans, Alexander Grigoriev, Eelko Penninkx, Ren Sitters,Thomas Wolle |
| |
| Affiliation: | aInstitute of Information and Computing Sciences, Utrecht University, P.O. Box 80.089, 3508 TB Utrecht, The Netherlands;bDepartment of Quantitative Economics, Maastricht University, P.O. Box 616, 6200 MD Maastricht, The Netherlands;cEindhoven University of Technology, Department of Mathematics and Computer Science, P.O. Box 513, 5600 MB Eindhoven, The Netherlands;dNICTA Sydney, Locked Bag 9013, Alexandria NSW 1435, Australia |
| |
| Abstract: | 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 a subexponential time exact algorithm. For the special case when the room connectivity graph is k-outerplanar the algorithm running time becomes cubic. 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. |
| |
| Keywords: | Minimum corridor connection Generalized geometric problems Complexity Exact algorithms Approximations |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
