Complexity of minimum corridor guarding problems
From MaRDI portal
Publication:456091
DOI10.1016/j.ipl.2012.06.003zbMath1248.68225OpenAlexW2038393491MaRDI 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
Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (2)
Cites Work
- 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
- 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
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Complexity of minimum corridor guarding problems
