Linear time approximation for dominating sets and independent dominating sets in unit disk graphs
DOI10.1007/978-3-642-38016-7_8zbMATH Open1395.68338OpenAlexW1603887547MaRDI QIDQ2848916FDOQ2848916
Authors: Guilherme D. Da Fonseca, Celina M. H. de Figueiredo, Vinícius G. P. De Sá, R. C. S. Machado 
Publication date: 13 September 2013
Published in: Approximation and Online Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-38016-7_8
Recommendations
- Efficient sub-5 approximations for minimum dominating sets in unit disk graphs
- Linear-time approximation algorithms for unit disk graphs
- Minimum dominating set problem for unit disks revisited
- A (4 + ε)-Approximation for the Minimum-Weight Dominating Set Problem in Unit Disk Graphs
- Constant-Factor Approximation for Minimum-Weight (Connected) Dominating Sets in Unit Disk Graphs
Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Cited In (11)
- Local PTAS for Dominating and Connected Dominating Set in Location Aware Unit Disk Graphs
- A new bound on maximum independent set and minimum connected dominating set in unit disk graphs
- Shifting coresets: obtaining linear-time approximations for unit disk graphs and other geometric intersection graphs
- Graph-Theoretic Concepts in Computer Science
- Efficient independent set approximation in unit disk graphs
- Minimum dominating set problem for unit disks revisited
- Faster approximation for maximum independent set on unit disk graph
- On the recognition of unit disk graphs and the distance geometry problem with ranges
- Linear-time approximation algorithms for unit disk graphs
- Randomized on-line algorithms and lower bounds for computing large independent sets in disk graphs
- The within-strip discrete unit disk cover problem
This page was built for publication: Linear time approximation for dominating sets and independent dominating sets in unit disk graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2848916)
