A polynomial‐time approximation scheme for the minimum‐connected dominating set in ad hoc wireless networks
Top Cited Papers
- 23 September 2003
- Vol. 42 (4) , 202-208
- https://doi.org/10.1002/net.10097
Abstract
A connected dominating set in a graph is a subset of vertices such that every vertex is either in the subset or adjacent to a vertex in the subset and the subgraph induced by the subset is connected. A minimum‐connected dominating set is such a vertex subset with minimum cardinality. An application in ad hoc wireless networks requires the study of the minimum‐connected dominating set in unit‐disk graphs. In this paper, we design a (1 + 1/s)‐approximation for the minimum‐connected dominating set in unit‐disk graphs, running in timenO((slogs)2).Keywords
This publication has 13 references indexed in Scilit:
- Dynamic Source Routing in Ad Hoc Wireless NetworksPublished by Springer Nature ,2007
- Message-optimal connected dominating sets in mobile ad hoc networksPublished by Association for Computing Machinery (ACM) ,2002
- Scenario-based performance analysis of routing protocols for mobile ad-hoc networksPublished by Association for Computing Machinery (ACM) ,1999
- On calculating connected dominating set for efficient routing in ad hoc wireless networksPublished by Association for Computing Machinery (ACM) ,1999
- CEDAR: a core-extraction distributed ad hoc routing algorithmIEEE Journal on Selected Areas in Communications, 1999
- Ad-hoc on-demand distance vector routingPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1999
- Approximation Algorithms for Connected Dominating SetsAlgorithmica, 1998
- Simple heuristics for unit disk graphsNetworks, 1995
- On the hardness of approximating minimization problemsJournal of the ACM, 1994
- Unit disk graphsDiscrete Mathematics, 1990