Complexity of minimum corridor guarding problems

DOI10.1016/j.ipl.2012.06.003zbMath1248.68225MaRDI QIDQ456091

Ning Xu

Publication date: 23 October 2012

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://academicworks.cuny.edu/cc_etds_theses/30

zbMATH Keywords

computational complexity; NP-complete; computational geometry; corridor guarding

Mathematics Subject Classification ID

68R10: Graph theory (including graph drawing) in computer science

68U05: Computer graphics; computational geometry (digital and algorithmic aspects)

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

Related Items

THE MINIMUM GUARDING TREE PROBLEM, Watchman routes for lines and line segments

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Minimum face-spanning subgraphs of plane graphs
• Approximating the tree and tour covers of a graph
• Shortest watchman routes in simple polygons
• On the minimum corridor connection problem and other generalized geometric problems
• Complexity of the minimum-length corridor problem
• Optimum watchman routes
• A better heuristic for orthogonal graph drawings
• Approximation algorithms for the watchman route and zookeeper's problems.
• Fast computation of shortest watchman routes in simple polygons
• A linear-time 2-approximation algorithm for the watchman route problem for simple polygons
• Approximating corridors and tours via restriction and relaxation techniques
• Touring a sequence of polygons
• The Rectilinear Steiner Tree Problem is $NP$-Complete
• AN INCREMENTAL ALGORITHM FOR CONSTRUCTING SHORTEST WATCHMAN ROUTES
• A Polylogarithmic Approximation Algorithm for the Group Steiner Tree Problem
• CORRIGENDUM TO "AN INCREMENTAL ALGORITHM FOR CONSTRUCTING SHORTEST WATCHMAN ROUTES"
• Concerning the time bounds of existing shortest watchman route algorithms
• Computing a shortest watchman path in a simple polygon in polynomial-time