APPROXIMATION ALGORITHMS FOR A VARIANT OF DISCRETE PIERCING SET PROBLEM FOR UNIT DISKS
From MaRDI portal
Publication:2932520
DOI10.1142/S021819591350009XzbMath1318.68182MaRDI QIDQ2932520
Paz Carmi, Minati De, Subhas C. Nandy, Gautam K. Das
Publication date: 1 December 2014
Published in: International Journal of Computational Geometry & Applications (Search for Journal in Brave)
Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)
Related Items (8)
Linear-Time Approximation Algorithms for Unit Disk Graphs ⋮ Minimum Dominating Set Problem for Unit Disks Revisited ⋮ Efficient independent set approximation in unit disk graphs ⋮ Algorithmic aspects of secure domination in unit disk graphs ⋮ Liar's dominating set problem on unit disk graphs ⋮ Liar’s Domination in 2D ⋮ Covering segments with unit squares ⋮ Vertex-edge domination in unit disk graphs
Cites Work
- Approximation algorithms for maximum independent set of pseudo-disks
- Improved results on geometric hitting set problems
- New approximations for minimum-weighted dominating sets and minimum-weighted connected dominating sets on unit disk graphs
- Minimum clique partition in unit disk graphs
- On domination and independent domination numbers of a graph
- A \(5+\varepsilon\)-approximation algorithm for minimum weighted dominating set in unit disk graph
- A better constant-factor approximation for weighted dominating set in unit disk graph
- Unit disk graphs
- Covering a set of points in multidimensional space
- Optimal output-sensitive convex hull algorithms in two and three dimensions
- Polynomial-time approximation schemes for piercing and covering with applications in wireless networks
- Approximation schemes for covering and packing problems in image processing and VLSI
- Simple heuristics for unit disk graphs
- Polynomial-time approximation schemes for packing and piercing fat objects
- ON THE DISCRETE UNIT DISK COVER PROBLEM
- The NP-completeness column: An ongoing guide
This page was built for publication: APPROXIMATION ALGORITHMS FOR A VARIANT OF DISCRETE PIERCING SET PROBLEM FOR UNIT DISKS
