Name
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. |
Year | DOI | Venue |
|---|---|---|
2006 | 10.1007/11814856_35 | WASA |
Keywords | Field | DocType |
dramatic improvement,maximal independent set,virtual backbone,localized convex-hull,important rule,resultant connected dominating set,sensor network,unit-disk graph,unit disk graph,convex hull,connected dominating set,dominating set | Graph theory,Discrete mathematics,Dominating set,Combinatorics,Cardinal number,Computer science,Cardinality,Convex hull,Algorithm,Independent set,Connected dominating set,Maximal independent set | Conference |
Volume | ISSN | ISBN |
4138 | 0302-9743 | 3-540-37189-3 |
Citations | PageRank | References |
4 | 0.46 | 8 |
Authors | ||
6 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Dechang Chen | 1 | 402 | 33.51 |
| Xilong Mao | 2 | 6 | 2.24 |
| Xia Fei | 3 | 4 | 0.46 |
| Xing Kai | 4 | 442 | 28.13 |
| Fang Liu | 5 | 397 | 20.61 |
| Min Song | 6 | 374 | 45.55 |