Complexity of the minimum-length corridor problem

DOI10.1016/J.COMGEO.2006.10.002MaRDI QIDQ876503zbMATH OpenOpenAlexFDO

Authors Arturo Gonzalez-Gutierrez, Teofilo F. Gonzalez

Publication date 18 April 2007

Published in Computational Geometry (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.comgeo.2006.10.002

zbMATH Keywords

minimum optical fiber lengthNP-completeness

Mathematics Subject Classification ID

Numerical aspects of computer graphics, image analysis, and computational geometry (65D18) Numerical mathematical programming methods (65K05) Complexity and performance of numerical algorithms (65Y20)

Review text

The authors study the minimum-length corridor (MLC) problem and some of its variants. More precisely, given a rectangular boundary partitioned into rectilinear polygons, the problem consists in finding a corridor of least total length. A corridor is a set of line segments each of which must lie along the line segments that form the rectangular boundary and/or the boundary of the rectilinear polygons. The corridor is a tree, and must include at least one point from the rectangular boundary and at least one point from the boundary of each of the rectilinear polygons. In this paper, it is established that the MLC problem is NP-complete.

Recommendations

• On the Minimum Corridor Connection Problem and Other Generalized Geometric Problems
• Approximating corridors and tours via restriction and relaxation techniques
• On the minimum corridor connection problem and other generalized geometric problems
• Complexity of minimum corridor guarding problems
• On heuristics for minimum length rectilinear partitions

Cites work

• An improved approximation scheme for the Group Steiner Problem
• Approximating the tree and tour covers of a graph
• scientific article; zbMATH DE number 139784 (Why is no real title available?)
• scientific article; zbMATH DE number 219265 (Why is no real title available?)
• On the complexity of approximating TSP with neighborhoods and related problems
• Planar Formulae and Their Uses
• Reducibility among combinatorial problems

Cited in

(6)

• Complexity and approximation results for the connected vertex cover problem in graphs and hypergraphs
• Complexity of minimum corridor guarding problems
• THE MINIMUM GUARDING TREE PROBLEM
• On the Minimum Corridor Connection Problem and Other Generalized Geometric Problems
• Minimum length corridor problem on grids
• On the minimum corridor connection problem and other generalized geometric problems

This page was built for publication: Complexity of the minimum-length corridor problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q876503)