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

NP-completenessminimum optical fiber length

Mathematics Subject Classification ID

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

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

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

Cited in

(5)

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

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)