Maximal Independent Set and Minimum Connected Dominating Set in Unit Disk Graphs
Lists
Only you see this
Abstract
In ad hoc wireless networks, the connected dominating set can be used as a virtual backbone to improve the performance. Many constructions for approximating the minimum connected dominating set are based on construction of maximal independent set. The relation between the size\nmis(G) of a maximum independent set and the size cds(G) of minimum connected dominating set in the same graph G plays an important role in establishing the performance ratio of those approximation algorithms. Previously, it is known that mis(G)<=4*cds(G)+1 for all unit disk graph G. In this paper, we improve it by showing mis(G)<=3.8*cds(G)+1.2.
BibTeX
@inproceedings{wuli2004maximal,
author = {Wei Wuli and Hongwei Du and Xiaohua Jia and Yingshu Li and Scott C.-H. Huang and Ding‐Zhu Du},
title = {{Maximal Independent Set and Minimum Connected Dominating Set in Unit Disk Graphs}},
booktitle = {University},
year = {2004},
}Loading related content...