Linear-Time 3-Approximation Algorithm for the r-Star Covering Problem
DOI10.1007/978-3-540-77891-2_15zbMATH Open1132.68821OpenAlexW1849516636MaRDI QIDQ5452162FDOQ5452162
Authors: Agnieszka Wasylewicz, Paweł Żyliński, Andrzej Lingas 
Publication date: 25 March 2008
Published in: WALCOM: Algorithms and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-540-77891-2_15
Recommendations
- Linear-time 3-approximation algorithm for the \(r\)-star covering problem
- Minimum \(r\)-star cover of class-3 orthogonal polygons
- Note on covering monotone orthogonal polygons with star-shaped polygons
- On covering orthogonal polygons with star-shaped polygons
- Covering orthogonal polygons with star polygons: The perfect graph approach
Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)
Cites Work
- The ellipsoid method and its consequences in combinatorial optimization
- Title not available (Why is that?)
- Semidefinite programming and integer programming
- Covering orthogonal polygons with star polygons: The perfect graph approach
- Some NP-hard polygon decomposition problems
- Covering Polygons Is Hard
- Title not available (Why is that?)
- POLYGON DECOMPOSITION AND THE ORTHOGONAL ART GALLERY PROBLEM
- Orthogonally convex covering of orthogonal polygons without holes
- Decomposing a Polygon into Simpler Components
- Perfect Graphs and Orthogonally Convex Covers
- On covering orthogonal polygons with star-shaped polygons
- Note on covering monotone orthogonal polygons with star-shaped polygons
- OPTIMUM GUARD COVERS AND m-WATCHMEN ROUTES FOR RESTRICTED POLYGONS
Cited In (4)
This page was built for publication: Linear-Time 3-Approximation Algorithm for the r-Star Covering Problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5452162)
