On the power of lookahead in greedy scheme for finding a minimum CDS for unit disk graphs
From MaRDI portal
Publication:2970204
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)
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
Cites work
- A Greedy Heuristic for the Set-Covering Problem
- 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
- Minimum connected dominating sets and maximal independent sets in unit disk graphs
- NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs
- Unit disk graphs
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)
