Minimum Dominating Set Problem for Unit Disks Revisited
DOI10.1142/S0218195915500132zbMath1344.68280OpenAlexW2193740829MaRDI QIDQ3459050
Prajwal R. Prasad, Yael Stein, Paz Carmi, Ramesh K. Jallu, Subhas C. Nandy, Gautam K. Das
Publication date: 30 December 2015
Published in: International Journal of Computational Geometry & Applications (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1142/s0218195915500132
Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25) Graph representations (geometric and intersection representations, etc.) (05C62)
Related Items (4)
Cites Work
- A note on two problems in connexion with graphs
- Space-efficient planar convex hull algorithms
- Improved results on geometric hitting set problems
- New approximations for minimum-weighted dominating sets and minimum-weighted connected dominating sets on unit disk graphs
- 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
- Polynomial-time approximation schemes for piercing and covering with applications in wireless networks
- APPROXIMATION ALGORITHMS FOR A VARIANT OF DISCRETE PIERCING SET PROBLEM FOR UNIT DISKS
- Approximation schemes for covering and packing problems in image processing and VLSI
- A Greedy Heuristic for the Set-Covering Problem
- Simple heuristics for unit disk graphs
- ON THE DISCRETE UNIT DISK COVER PROBLEM
- The Densest Packing of 9 Circles in a Square
- The NP-completeness column: An ongoing guide
This page was built for publication: Minimum Dominating Set Problem for Unit Disks Revisited
