Tighter Approximation Bounds for Minimum CDS in Wireless Ad Hoc Networks

DOI10.1007/978-3-642-10631-6_71zbMath1273.68411OpenAlexW1592922472MaRDI QIDQ3652256

Peng-Jun Wan, Minming Li, 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

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

Related Items (10)

Unnamed Item ⋮ Approximation algorithms for load-balanced virtual backbone construction in wireless sensor networks ⋮ A new bound on maximum independent set and minimum connected dominating set in unit disk graphs ⋮ A greedy algorithm for the fault-tolerant connected dominating set in a general graph ⋮ Algorithmic aspects of secure domination in unit disk graphs ⋮ Secure connected domination and secure total domination in unit disk graphs and rectangle graphs ⋮ Wireless networking, dominating and packing ⋮ Computing Minimum k-Connected m-Fold Dominating Set in General Graphs ⋮ Locating battery charging stations to facilitate almost shortest paths ⋮ Some results for the two disjoint connected dominating sets problem

This page was built for publication: Tighter Approximation Bounds for Minimum CDS in Wireless Ad Hoc Networks