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

در شبکه حسگر بی سیم وقتی که همه حسگرها دارای شعاع ارتباطی یکسانی باشند، از گراف دیسک واحد برای مدل سازی آن شبکه استفاده می‌شود. به این ترتیب دو مساله بهینه سازی زیر مورد تحقیق محققان واقع شده است: مجموعه مستقل ماکزیمال در شبکه و مینیمال مجموعه احاطه کننده شبکه. با توجه به NP- سخت بودن هر دو مساله فوق، الگوریتم‌های متعددی برای تقریب آنها تا کنون ارایه شده است. گراف لانه زنبوری مسطح از به هم پیوستن تعدادی شش ضلعی منتظم به دست می آید، به طوری که دو شش ضلعی مجاور دارای یک لبه مشترک هستند. چندین مطالعه در مورد رفتار ساختار لانه زنبوری انجام شده است. تعداد نتایج در این زمینه زیاد و همواره در حال افزایش است. در این مقاله، با استفاده از گراف لانه زنبوری و روش‌های ماتریسی، الگوریتمی برای تقریب مجموعه مستقل ماکزیمال شبکه ارایه داده ایم. اگر گراف کران دار باشد مساله های مد نظر را می توان در زمان چند جمله ای حل کرد. در پایان نیز، درستی الگوریتم و پیچیدگی آن را به دست آورده و با یک مثال عددی آن را بررسی کرده ایم.