On the Power of Lookahead in Greedy Scheme for Finding a Minimum CDS for Unit Disk Graphs

DOI10.1142/S0129054116500325zbMath1404.68085OpenAlexW2581245158MaRDI QIDQ2970204

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

zbMATH Keywords

greedy algorithmconnected dominating setperformance ratiounit disk graph

Mathematics Subject Classification ID

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