A Convex-Hull Based Algorithm to Connect the Maximal Independent Set in Unit-Disk Graphs

by: Dechang Chen, Xilong Mao, Xia Fei, Kai Xing, Fang Liu, Min Song

Wireless Algorithms, Systems, and Applications (2006), pp. 363-370.

View FullText article

Springer (DOI)

Reviews [Write a review of this article]

There are no reviews of this article

Find related articles from these CiteULike users

AbnerCYH

Find related articles with these CiteULike tags

algorithms, geometries, graph

Abstract

In this paper we propose and analyze a localized convex-hull based algorithm to connect a maximal independent set. The cardinality of the resultant connected dominating set is at most 76opt +19, where opt is the size of a minimum connected dominating set. To our knowledge, this is a dramatic improvement compared to the best published results in the same context [1,6] . Our algorithm plays an important rule in efficiently constructing a virtual backbone for ad hoc and sensor networks. Keywords: Ad hoc and sensor networks, maximal independent set, connected dominating set.

@incollection{citeulike:1724309, abstract = {In this paper we propose and analyze a localized convex-hull based algorithm to connect a maximal independent set. The cardinality of the resultant connected dominating set is at most 76opt +19, where opt is the size of a minimum connected dominating set. To our knowledge, this is a dramatic improvement compared to the best published results in the same context [1,6] . Our algorithm plays an important rule in efficiently constructing a virtual backbone for ad hoc and sensor networks. Keywords: Ad hoc and sensor networks, maximal independent set, connected dominating set.}, author = {Chen, Dechang and Mao, Xilong and Fei, Xia and Xing, Kai and Liu, Fang and Song, Min }, citeulike-article-id = {1724309}, doi = {10.1007/11814856\_35}, journal = {Wireless Algorithms, Systems, and Applications}, keywords = {algorithms, geometries, graph}, pages = {363--370}, posted-at = {2007-10-03 15:32:14}, priority = {2}, title = {A Convex-Hull Based Algorithm to Connect the Maximal Independent Set in Unit-Disk Graphs}, url = {http://dx.doi.org/10.1007/11814856\_35}, year = {2006} }

RIS record

TY - CHAP ID - citeulike:1724309 L3 - citeulike-article-id:1724309 TI - A Convex-Hull Based Algorithm to Connect the Maximal Independent Set in Unit-Disk Graphs JF - Wireless Algorithms, Systems, and Applications SP - 363 EP - 370 N2 - In this paper we propose and analyze a localized convex-hull based algorithm to connect a maximal independent set. The cardinality of the resultant connected dominating set is at most 76opt +19, where opt is the size of a minimum connected dominating set. To our knowledge, this is a dramatic improvement compared to the best published results in the same context [1,6] . Our algorithm plays an important rule in efficiently constructing a virtual backbone for ad hoc and sensor networks. Keywords: Ad hoc and sensor networks, maximal independent set, connected dominating set. KW - algorithms KW - geometries KW - graph AU - Chen, Dechang AU - Mao, Xilong AU - Fei, Xia AU - Xing, Kai AU - Liu, Fang AU - Song, Min PY - 2006/// UR - http://dx.doi.org/10.1007/11814856_35 ER -

RIS BibTeX