Complexity of minimum corridor guarding problems
From MaRDI portal
Publication:456091
DOI10.1016/j.ipl.2012.06.003zbMath1248.68225MaRDI QIDQ456091
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
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
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