Complexity of minimum corridor guarding problems

DOI10.1016/J.IPL.2012.06.003zbMATH Open1248.68225OpenAlexW2038393491MaRDI QIDQ456091FDOQ456091

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

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

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)

Cites Work

• Title not available (Why is that?)
• A Polylogarithmic Approximation Algorithm for the Group Steiner Tree Problem
• The Rectilinear Steiner Tree Problem is $NP$-Complete
• Title not available (Why is that?)
• A better heuristic for orthogonal graph drawings
• A linear-time 2-approximation algorithm for the watchman route problem for simple polygons
• Touring a sequence of polygons
• AN INCREMENTAL ALGORITHM FOR CONSTRUCTING SHORTEST WATCHMAN ROUTES
• Shortest watchman routes in simple polygons
• Optimum watchman routes
• Fast computation of shortest watchman routes in simple polygons
• Title not available (Why is that?)
• Approximation algorithms for the watchman route and zookeeper's problems.
• Approximating corridors and tours via restriction and relaxation techniques
• Title not available (Why is that?)
• Title not available (Why is that?)
• 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
• Minimum face-spanning subgraphs of plane graphs
• Approximating the tree and tour covers of a graph
• On the minimum corridor connection problem and other generalized geometric problems
• Complexity of the minimum-length corridor problem

Cited In (5)

• THE MINIMUM GUARDING TREE PROBLEM
• On Some City Guarding Problems
• 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

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)