On the power of lookahead in greedy scheme for finding a minimum CDS for unit disk graphs
DOI10.1142/S0129054116500325zbMATH Open1404.68085OpenAlexW2581245158MaRDI QIDQ2970204FDOQ2970204
Authors: Satoshi Fujita 
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
Recommendations
- Tighter approximation bounds for minimum CDS in unit disk graphs
- Revisiting connected dominating sets: an optimal local algorithm?
- A greedy algorithm for the minimum \(2\)-connected \(m\)-fold dominating set problem
- Minimum connected dominating sets and maximal independent sets in unit disk graphs
- Approximation algorithms for highly connected multi-dominating sets in unit disk graphs
Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph representations (geometric and intersection representations, etc.) (05C62)
Cites Work
- A Greedy Heuristic for the Set-Covering Problem
- Unit disk graphs
- Minimum connected dominating sets and maximal independent sets in unit disk graphs
- A polynomial-time approximation scheme for the minimum-connected dominating set in ad hoc wireless networks
- Approximation algorithms for connected dominating sets
- Improving construction for connected dominating set with Steiner tree in wireless sensor networks
- NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs
Cited In (1)
This page was built for publication: On the power of lookahead in greedy scheme for finding a minimum CDS for unit disk graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2970204)
