A polynomial-time approximation scheme for the minimum-connected dominating set in ad hoc wireless networks.

*(English)*Zbl 1031.05092Summary: 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 time \(n^{O((s \log s)^2)}\).

##### MSC:

05C69 | Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) |

05C85 | Graph algorithms (graph-theoretic aspects) |

Full Text:
DOI

##### References:

[1] | and New distributed algorithm for connected dominating set in wireless ad hoc networks, Proc HICSS, Hawaii, 2002, pp. 3881-3887. |

[2] | and Load-balancing clusters in wireless ad hoc networks, Proc 3rd IEEE Symp on Application-Specific Systems and Software Engineering Technology, 2000, pp. 25-32. |

[3] | and Virtual backbone-based routing in ad hoc wireless networks, Technical report 02-002, Department of Computer Science and Engineering, University of Minnesota. |

[4] | Clark, Discr Math 86 pp 165– (1990) |

[5] | and Optimized link state routing protocol, IETF Internet Draft, draft-ietf-manet-olsr-05.txt, October 2001. |

[6] | and Routing in ad hoc networks using minimum connected dominating sets, ICC ’97, Montreal, Canada, June 1997, pp. 376-380. |

[7] | Guha, Algorithmica 20 pp 374– (1998) |

[8] | and Scenario-based performance analysis of routing protocols for mobile ad hoc networks, Proc IEEE MOBICOM, Seattle, August 1999, pp. 195-206. |

[9] | and ? Dynamic source routing in ad hoc wireless networks,? Mobile computing, and (Editors), Kluwer, Boston, 1996, pp. 153-181. |

[10] | Lund, J ACM 41 pp 960– (1994) |

[11] | Marathe, Networks 25 pp 59– (1995) |

[12] | and The broadcast storm problem in a mobile ad hoc network, Proc MOBICOM, Seattle, 1999, pp. 151-162. |

[13] | and Ad hoc on-demand distance vector routing, Proc 2nd IEEE Workshop on Mobile Computing Systems and Applications, New Orleans, LA, February 1999, pp. 90-100. |

[14] | Sinha, INFOCOM 3 pp 1763– (2001) |

[15] | Sivakumar, IEEE J Sel Areas Commun 17 pp 1454– (1999) |

[16] | and On calculating connected dominating set for efficient routing in ad hoc wireless networks, Proc 3rd Int Workshop on Discrete Algorithms and Methods for MOBILE Computing and Communications, Seattle, WA, 1999, pp. 7-14. |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.