Linear time approximation for dominating sets and independent dominating sets in unit disk graphs

DOI10.1007/978-3-642-38016-7_8MaRDI QIDQ2848916zbMATH OpenOpenAlexFDO

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

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

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

Cited in

(12)

• Efficient sub-5 approximations for minimum dominating sets in unit disk graphs
• 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
• Efficient independent set approximation in unit disk graphs
• Graph-Theoretic Concepts in Computer Science
• 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)