يک روش هندسي براي پيدا کردن کران جديد روي مجموعه مستقل ماکسيمال و مجموعه احاطه¬گر همبند مينيمال در يک گراف ديسک واحد

الموضوعات :

غلام حسن شیردل ¹ , مهدی جالینوسی ²

1 - گروه ریاضی، دانشکده علوم، دانشگاه قم، قم، ایران
2 - گروه ریاضی، دانشکده علوم، دانشگاه قم، قم، ایران

تاريخ الإرسال : 16 الخميس , جمادى الأولى, 1442 تاريخ التأكيد : 07 الإثنين , ربيع الأول, 1444 تاريخ الإصدار : 28 الخميس , جمادى الأولى, 1444

الکلمات المفتاحية: Independent number, Unit disk graph, Connected domination number, Maximal independent set, Connected dominating set,

ملخص المقالة :

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

المصادر:

[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