On the power of lookahead in greedy scheme for finding a minimum CDS for unit disk graphs
From MaRDI portal
(Redirected from Publication:2970204)
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)
