Tighter approximation bounds for minimum CDS in wireless ad hoc networks

DOI10.1007/978-3-642-10631-6_71MaRDI QIDQ3652256zbMATH OpenOpenAlexFDO

Authors Minming Li, Peng-Jun Wan, Frances F. Yao

Publication date 17 December 2009

Published in Algorithms and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-10631-6_71

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Recommendations

• Tighter approximation bounds for minimum CDS in unit disk graphs
• Minimum connected dominating sets and maximal independent sets in unit disk graphs
• Theoretical Bound and Practical Analysis of Connected Dominating Set in Ad Hoc and Sensor Networks
• ANALYSIS ON THEORETICAL BOUNDS FOR APPROXIMATING DOMINATING SET PROBLEMS
• On approximation algorithms of \(k\)-connected \(m\)-dominating sets in disk graphs

Cited in

(16)

• Locating battery charging stations to facilitate almost shortest paths
• Wireless networking, dominating and packing
• Secure connected domination and secure total domination in unit disk graphs and rectangle graphs
• Theoretical Bound and Practical Analysis of Connected Dominating Set in Ad Hoc and Sensor Networks
• ANALYSIS ON THEORETICAL BOUNDS FOR APPROXIMATING DOMINATING SET PROBLEMS
• Approximation algorithms for load-balanced virtual backbone construction in wireless sensor networks
• A greedy algorithm for the fault-tolerant connected dominating set in a general graph
• Computing Minimum k-Connected m-Fold Dominating Set in General Graphs
• Some results for the two disjoint connected dominating sets problem
• Locating battery charging stations to facilitate almost shortest paths
• Algorithmic aspects of secure domination in unit disk graphs
• Tighter approximation bounds for minimum CDS in unit disk graphs
• A survey on variant domination problems in geometric intersection graphs
• Minimum connected dominating sets and maximal independent sets in unit disk graphs
• A new bound on maximum independent set and minimum connected dominating set in unit disk graphs
• A better approximation for constructing virtual backbone in 3D wireless ad-hoc networks

This page was built for publication: Tighter approximation bounds for minimum CDS in wireless ad hoc networks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3652256)