Complexity of the minimum-length corridor problem

DOI10.1016/j.comgeo.2006.10.002zbMath1117.65035OpenAlexW2038002703MaRDI QIDQ876503

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

NP-completenessminimum optical fiber length

Mathematics Subject Classification ID

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

Related Items (4)

On the minimum corridor connection problem and other generalized geometric problems ⋮ Complexity of minimum corridor guarding problems ⋮ THE MINIMUM GUARDING TREE PROBLEM ⋮ Complexity and approximation results for the connected vertex cover problem in graphs and hypergraphs

Cites Work

• Approximating the tree and tour covers of a graph
• An improved approximation scheme for the Group Steiner Problem
• Planar Formulae and Their Uses
• Reducibility among Combinatorial Problems
• Algorithms - ESA 2003
• Unnamed Item
• Unnamed Item

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