آمار
| تعداد نشریات | 50 |
| تعداد شماره‌ها | 2,079 |
| تعداد مقالات | 19,525 |
| تعداد مشاهده مقاله | 22,854,946 |
| تعداد دریافت فایل اصل مقاله | 21,106,314 |
Improvment Upper Bound of the Independence Nnmber of Maximum Independent Set in Unit Disk Graph | ||
| Journal of New Researches in Mathematics | ||
| مقاله 15، دوره 8، شماره 36، آذر و دی 2022، صفحه 177-180 اصل مقاله (822.37 K) | ||
| نوع مقاله: research paper | ||
| شناسه دیجیتال (DOI): 10.30495/jnrm.2022.58031.2028 | ||
| نویسندگان | ||
Gholam Hassan Shirdel   ؛ mehdi G jalinousi
| ||
| Department of Mathematics, Faculty of Science, University of Qom, Qom, Iran | ||
| چکیده | ||
| 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. | ||
| کلیدواژه‌ها | ||
| Connected dominating set؛ Independent number؛ Unit disk graph؛ Maximal independent set؛ Connected domination number | ||
| مراجع | ||
|
[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
|
|
|
|
||
|
|
||
آمار
تعداد مشاهده مقاله: 109
تعداد دریافت فایل اصل مقاله: 12