|
|
|
|
الگوریتم شبه کد برای تقریب مجموعه مستقل ماکزیمال در گراف دیسک واحد
|
|
|
|
|
|
|
|
نویسنده
|
شیردل غلام حسن ,قنبری مجتبی ,جالینوسی مهدی
|
|
منبع
|
پژوهش هاي نوين در رياضي - 1399 - دوره : 6 - شماره : 27 - صفحه:17 -26
|
|
چکیده
|
در شبکه حسگر بی سیم وقتی که همه حسگرها دارای شعاع ارتباطی یکسانی باشند، از گراف دیسک واحد برای مدل سازی آن شبکه استفاده می شود. به این ترتیب دو مساله بهینه سازی زیر مورد تحقیق محققان واقع شده است: مجموعه مستقل ماکزیمال در شبکه و مینیمال مجموعه احاطه کننده شبکه. با توجه به np- سخت بودن هر دو مساله فوق، الگوریتم های متعدّدی برای تقریب آنها تا کنون ارائه شده است. گراف لانه زنبوری مسطح از به هم پیوستن تعدادی شش ضلعی منتظم به دست می آید، به طوری که دو شش ضلعی مجاور دارای یک لبه مشترک هستند. چندین مطالعه در مورد رفتار ساختار لانه زنبوری انجام شده است. تعداد نتایج در این زمینه زیاد و همواره در حال افزایش است. در این مقاله، با استفاده از گراف لانه زنبوری و روش های ماتریسی، الگوریتمی برای تقریب مجموعه مستقل ماکزیمال شبکه ارائه داده ایم. اگر گراف کران دار باشد مساله های مد نظر را می توان در زمان چند جمله ای حل کرد. در پایان نیز، درستی الگوریتم و پیچیدگی آن را به دست آورده و با یک مثال عددی آن را بررسی کرده ایم.
|
|
کلیدواژه
|
شبکه بی سیم، مجموعه مستقل، مجموعه احاطه گر، الگوریتم، شبکه لانه زنبوری
|
|
آدرس
|
دانشگاه قم, دانشکده علوم, گروه ریاضی, ایران, دانشگاه آزاد اسلامی واحد فراهان, گروه ریاضی, ایران, دانشگاه قم, دانشکده علوم, گروه ریاضی, ایران
|
|
پست الکترونیکی
|
9125550779
|
|
|
|
|
|
|
|
|
|
|
|
|
|
a algorithm pseudo code for approximating of maximal independent set in the unit disc graph
|
|
|
|
|
Authors
|
shirdel gholam hassan ,ghanbari mojtaba ,jalinousi mehdi
|
|
Abstract
|
the unit disk graph is used to model a wireless sensor network when all sensors have the same communication radius. hence, the following two optimization problems have been investigated by the researchers: maximal independent set in the network and minimal network dominating set. since these problems are np-hard, several algorithms have been presented for their approximation. in this paper, we have presented a honeycomb graph and algorithmic matrix methods for approximating the maximal independent set in the network. finally, we have confirmed the validity of the algorithm and its complexity and studied it with a numerical example.keywords: wireless network, independent set, dominating set, algorithm, honeycomb network e. leeuwen, approximation algorithms for unit disk graphs, technical report, institute of information and computing sciences, utrecht university, (2004), uu-cs-2004-066. n. bourgeois, f. della croce, b. escoffier. v.th. paschos, fast algorithms for min inde pendent dominating set, discrete applied mathematics 161, (2013), pp. 558-572.
|
|
Keywords
|
keywords: wireless network ,dominating set ,honeycomb network ,independent set ,algorithm
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|