THE MINIMUM GUARDING TREE PROBLEM

DOI10.1142/S1793830914500116zbMath1297.68263OpenAlexW2089927779MaRDI QIDQ5411806

Joseph S. B. Mitchell, Paweł Żyliński, Adrian Dumitrescu

Publication date: 25 April 2014

Published in: Discrete Mathematics, Algorithms and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s1793830914500116

zbMATH Keywords

approximation algorithmNP-hardnessguarding tree problem

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Related Items

Graphs with equal domination and covering numbers ⋮ The searchlight problem for road networks

Cites Work

• Unnamed Item
• Complexity of minimum corridor guarding problems
• Guarding a set of line segments in the plane
• On the minimum corridor connection problem and other generalized geometric problems
• Cooperative mobile guards in grids
• Complexity of the minimum-length corridor problem
• On gallery watchmen in grids
• Illuminating disjoint line segments in the plane
• Covering grids and orthogonal polygons with periscope guards
• Watchman routes for lines and line segments
• The Rectilinear Steiner Tree Problem is $NP$-Complete
• A Polylogarithmic Approximation Algorithm for the Group Steiner Tree Problem
• On Steiner’s Problem with Rectilinear Distance
• A tight bound on approximating arbitrary metrics by tree metrics
• Illumination in the presence of opaque line segments in the plane