On the Power of Lookahead in Greedy Scheme for Finding a Minimum CDS for Unit Disk Graphs
Publication:2970204
DOI10.1142/S0129054116500325zbMath1404.68085OpenAlexW2581245158MaRDI QIDQ2970204
Publication date: 28 March 2017
Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1142/s0129054116500325
Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25) Graph representations (geometric and intersection representations, etc.) (05C62)
Cites Work
- Minimum connected dominating sets and maximal independent sets in unit disk graphs
- Unit disk graphs
- Approximation algorithms for connected dominating sets
- Improving construction for connected dominating set with Steiner tree in wireless sensor networks
- A Greedy Heuristic for the Set-Covering Problem
- NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs
- A polynomial-time approximation scheme for the minimum-connected dominating set in ad hoc wireless networks
This page was built for publication: On the Power of Lookahead in Greedy Scheme for Finding a Minimum CDS for Unit Disk Graphs