Complexity of minimum corridor guarding problems

<a class="pub-badge pub-badge--doi" href="https://doi.org/10.1016/J.IPL.2012.06.003" rel="nofollow">DOI 10.1016/J.IPL.2012.06.003</a><a class="pub-badge pub-badge--grey" href="https://zbmath.org/1248.68225" rel="nofollow">zbMATH</a><a class="pub-badge pub-badge--grey" href="https://openalex.org/works/W2038393491" rel="nofollow">OpenAlex</a><a class="pub-badge pub-badge--mardi" href="https://portal.mardi4nfdi.de/wiki/Item:Q456091" rel="nofollow">MaRDI QID Q456091</a><a class="pub-badge pub-badge--grey" href="https://fdo.portal.mardi4nfdi.de/fdo/Q456091" rel="nofollow">FDO</a>

Authors 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 complexitycomputational geometryNP-completecorridor guarding

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• Complexity of the minimum-length corridor problem
• On the Minimum Corridor Connection Problem and Other Generalized Geometric Problems
• THE MINIMUM GUARDING TREE PROBLEM
• Guarding a set of line segments in the plane
• Computational complexity of art gallery problems

Cites work

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

Cited in

(5)

• Watchman routes for lines and line segments
• On the minimum corridor connection problem and other generalized geometric problems
• On the Minimum Corridor Connection Problem and Other Generalized Geometric Problems
• THE MINIMUM GUARDING TREE PROBLEM
• On Some City Guarding Problems

This page was built for publication: Complexity of minimum corridor guarding problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q456091)