A convex-hull based algorithm to connect the maximal independent set in unit-disk graphs

Dechang Chen; Xilong Mao; Xia Fei; Kai Xing; Fang Liu; Min Song

doi:10.1007/11814856_35

A convex-hull based algorithm to connect the maximal independent set in unit-disk graphs

Dechang Chen^*, Xilong Mao, Xia Fei, Kai Xing, Fang Liu, Min Song

^*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

7 Scopus citations

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 76 · opt + 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.

Original language	English
Title of host publication	Wireless Algorithms, Systems, and Applications - First International Conference, WASA 2006, Proceedings
Publisher	Springer Verlag
Pages	363-370
Number of pages	8
ISBN (Print)	3540371893, 9783540371892
DOIs	https://doi.org/10.1007/11814856_35
State	Published - 2006
Externally published	Yes
Event	First International Conference on Wireless Algorithms, Systems, and Applications, WASA 2006 - Xi'an, China Duration: 15 Aug 2006 → 17 Aug 2006

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	4138 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	First International Conference on Wireless Algorithms, Systems, and Applications, WASA 2006
Country/Territory	China
City	Xi'an
Period	15/08/06 → 17/08/06

Keywords

Ad hoc and sensor networks
Connected dominating set
Maximal independent set

Access to Document

10.1007/11814856_35

Cite this

Chen, D., Mao, X., Fei, X., Xing, K., Liu, F., & Song, M. (2006). A convex-hull based algorithm to connect the maximal independent set in unit-disk graphs. In Wireless Algorithms, Systems, and Applications - First International Conference, WASA 2006, Proceedings (pp. 363-370). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4138 LNCS). Springer Verlag. https://doi.org/10.1007/11814856_35

Chen, Dechang ; Mao, Xilong ; Fei, Xia et al. / A convex-hull based algorithm to connect the maximal independent set in unit-disk graphs. Wireless Algorithms, Systems, and Applications - First International Conference, WASA 2006, Proceedings. Springer Verlag, 2006. pp. 363-370 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{c560c08f584a4b48b0597df678734986,

title = "A convex-hull based algorithm to connect the maximal independent set in unit-disk graphs",

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 76 · opt + 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, Connected dominating set, Maximal independent set",

author = "Dechang Chen and Xilong Mao and Xia Fei and Kai Xing and Fang Liu and Min Song",

year = "2006",

doi = "10.1007/11814856_35",

language = "English",

isbn = "3540371893",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "363--370",

booktitle = "Wireless Algorithms, Systems, and Applications - First International Conference, WASA 2006, Proceedings",

note = "First International Conference on Wireless Algorithms, Systems, and Applications, WASA 2006 ; Conference date: 15-08-2006 Through 17-08-2006",

}

Chen, D, Mao, X, Fei, X, Xing, K, Liu, F & Song, M 2006, A convex-hull based algorithm to connect the maximal independent set in unit-disk graphs. in Wireless Algorithms, Systems, and Applications - First International Conference, WASA 2006, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 4138 LNCS, Springer Verlag, pp. 363-370, First International Conference on Wireless Algorithms, Systems, and Applications, WASA 2006, Xi'an, China, 15/08/06. https://doi.org/10.1007/11814856_35

A convex-hull based algorithm to connect the maximal independent set in unit-disk graphs. / Chen, Dechang; Mao, Xilong; Fei, Xia et al.
Wireless Algorithms, Systems, and Applications - First International Conference, WASA 2006, Proceedings. Springer Verlag, 2006. p. 363-370 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4138 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - A convex-hull based algorithm to connect the maximal independent set in unit-disk graphs

AU - Chen, Dechang

AU - Mao, Xilong

AU - Fei, Xia

AU - Xing, Kai

AU - Liu, Fang

AU - Song, Min

PY - 2006

Y1 - 2006

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 76 · opt + 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.

AB - 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 76 · opt + 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.

KW - Ad hoc and sensor networks

KW - Connected dominating set

KW - Maximal independent set

UR - http://www.scopus.com/inward/record.url?scp=33749668882&partnerID=8YFLogxK

U2 - 10.1007/11814856_35

DO - 10.1007/11814856_35

M3 - Conference contribution

AN - SCOPUS:33749668882

SN - 3540371893

SN - 9783540371892

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 363

EP - 370

BT - Wireless Algorithms, Systems, and Applications - First International Conference, WASA 2006, Proceedings

PB - Springer Verlag

T2 - First International Conference on Wireless Algorithms, Systems, and Applications, WASA 2006

Y2 - 15 August 2006 through 17 August 2006

ER -

Chen D, Mao X, Fei X, Xing K, Liu F, Song M. A convex-hull based algorithm to connect the maximal independent set in unit-disk graphs. In Wireless Algorithms, Systems, and Applications - First International Conference, WASA 2006, Proceedings. Springer Verlag. 2006. p. 363-370. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/11814856_35

A convex-hull based algorithm to connect the maximal independent set in unit-disk graphs

Abstract

Publication series

Conference

Keywords

Access to Document

Fingerprint

Cite this