On the power of lookahead in greedy scheme for finding a minimum CDS for unit disk graphs
From MaRDI portal
Graph representations (geometric and intersection representations, etc.) (05C62) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)
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)
