Improvment Upper Bound of the Independence Nnmber of Maximum Independent Set in Unit Disk Graph
Subject Areas : Statistics
Gholam Hassan Shirdel
1
(
Department of Mathematics, Faculty of Science, University of Qom, Qom, Iran
)
mehdi jalinousi
2
(
Department of Mathematics, Faculty of Science, University of Qom, Qom, Iran
)
Keywords: مجموعه احاطه گر همبند- عدد استقلال &ndash, گراف دیسک واحد- مجموعه مستقل ماکسیمال- عدد احاطه گرهمبند,
Abstract :
In a unit disk graph two vertices are adjacent if the distance between them is less than or equal to one with a two-dimensional Euclidean meter. The size of the maximal independent set in a graph G is called the independent number denoted by α(G). The size of the minimal connected dominating set in a graph G is called the connected domination number denoted by γ_c^((G)). A subset S of vertices in a graph is called a dominating set if every vertex is either in the subset or adjacent to a vertex in the S. A dominating set is connected if it induces a connected subgraph. A connected dominating set is often used as a virtual backbone in wireless sensor networks to improve communication and storage performance. Clearly the smaller virtual backbone gives the better performance.However computing a minimal connected dominating set is NP-hard. In other hand relation between the size of the minimal connected dominating set in a graph G is very important. The aim of this paper is to determine two better upper bounds of the independence number dependent on the connected domination number for a unit disk graph. Further we improve the upper bound to obtain the best bound with respect to the upper bounds obtained thus far.
|
[1] |
C. C. J. J. D. S. Clark B. N., "Unit disk graphs," Discrete Mathematics, 86, pp. 165-177, 1990. |
|
[2] |
Wan P . J., Alzoubi K. M., Frierder o., "Distributed constrution on of connected dominating set in wireless ad hoc networks," ACM/ Springer Mobile Network , pp. 141-149, 2004. |
|
[3] |
Wan P. J., Wang L., Yao F.F.,s "Two phased approximation algorithm s for minium CDS in wirelees ad hoc networks ICDCS," IEEE, pp. 3374-344, 2008. |
|
[4] |
K. A. M. U. S. M. Funke S., "Asimple improved distributed algorithm for minimum CD S in unit disk graphs," ACM T rans. Sensor N et, pp. 4444-453, 2006. |
|
[5] |
D. Dai and C. Yu, "A (5 +€)-approximation algorithm for minimum weighted dominatings set in unit disk graph ," Theor. Com put. Sci., p. 756–765, 2009. |
|
[6] |
Wu W., Du H., jia X., Li Y., Huang S., "Minimum c onnected dominating sets and maximal independent sets in unit disk graphs," Theor. Comput. Sci., pp. 1-7, 2006.
Li M., Wan P.J., Yao F., "Tighter Approximation Bonds for Minimum CDS in Unit Disk Graphs," Algorithmica 61(4), pp. 1000-1021, 2011. 2, 10, 12, 13, 29 |
|
|
|
|
|