Complexity of the minimum-length corridor problem

DOI10.1016/J.COMGEO.2006.10.002zbMATH Open1117.65035OpenAlexW2038002703MaRDI QIDQ876503FDOQ876503

Teofilo F. Gonzalez, Arturo Gonzalez-Gutierrez

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

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

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)

Cites Work

• Reducibility among Combinatorial Problems
• Planar Formulae and Their Uses
• An improved approximation scheme for the Group Steiner Problem
• Title not available (Why is that?)
• Approximating the tree and tour covers of a graph
• Algorithms - ESA 2003
• Title not available (Why is that?)

Cited In (5)

• 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
• 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)