بهبود کران بالای عدد استقلال مجموعه مستقل ماکزیمال در گراف دیسک واحد

محورهای موضوعی : آمار

غلام حسن شیردل ¹ (گروه ریاضی، دانشکده علوم، دانشگاه قم، قم، ایران)
مهدی جالینوسی ² (گروه ریاضی، دانشکده علوم، دانشگاه قم، قم، ایران)

تاریخ دریافت : 1399/10/11 تاریخ پذیرش : 1401/07/11 تاریخ انتشار : 1401/10/01

کلید واژه: Independent number, Unit disk graph, Connected domination number, Maximal independent set, Connected dominating set,

چکیده مقاله :

در یک گراف دیسک واحد دو رأس مجاورند اگر با متر اقلیدسی دو بعدی فاصله بین آنها کوچکتر یا مساوی یک باشد. اندازه مجموعه مستقل ماکسیمال در یک گرافG را عدد استقلال گفته و با α(G) نشان می دهیم. اندازه مجموعه احاطه گر همبند مینیمال در گراف G را عدد احاطه گر همبند می گفته و با γ_c (G) نمایش می دهیم. واضح است اگر فاصله بین دو گره از یک گراف دیسک واحد بیشتر از یک باشد آن دو گره مسقل هستند. یک زیر مجموعه S از راس ها در یک گراف مجموعه احاطه گر نامیده می شود اگر هر راس از گراف G یا عضو مجموعه S باشد یا با عضوی از آن مجاور باشد. یک مجموعه احاطه گر همبند است اگر یک زیر گراف همبند القا کند. یک مجموعه احاطه گر همبند اغلب به عنوان یک دکل مجازی در شبکه های سنسور بی سیم جهت بهبود ارتباطات و کارایی یهتر استفاده می شود. واضح است که دکل مجازی کوچکتر کارایی بهتری دارد. با این حال محاسبه یک مجموعه احاطه گر همبند مینیمال همچنان NP-سخت است. از طرفی ارتباط بین اندازه مجموعه مستقل ماکسیمال و اندازه مجموعه احاطه گر همبند مینیمال در یک گراف G بسیار اهمیت دارد. هدف اصلی این مقاله بهبود بخشیدن به کران بالای عدد استقلال وابسته به عدد احاطه گر همبند برای یک گراف دیسک واحد است. بعلاوه ما کران بالای موجود تا کنون را بهبود داده ایم.

چکیده انگلیسی:

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