مجموعه مستقل بیشینه

مسئله یافتن مجموعه مستقل بیشینه در گراف، یکی از مسائل کلاسیک در نظریه گراف است که کاربردهای فراوانی درحل مسائل دنیای واقعی دارد. در این مقاله روشی برای یافتن مجموعه مستقل بیشینه در گراف مورد بررسی قرار می گیرد.در ابتدا تعاریفی در مورد این مسئله بیان میشود. الگوریتم ترتیبی و غیرموازی که برای آن وجود دارد بررسی و برنامهسازی خواهد شد. الگوریتم ها و روش های موازی که تاکنون وجود داشته بررسی میشوند. در پایان هم یک برنامه موازیجدید با استاندارد ام پی آی شرح داده می شود. برای اجرای برنامه ها هم از یک سیستم تا تعداد ۳۲ پردازنده استفاده شده ونتایج اجرای برنامه ترتیبی و موازی بر روی سیستم، در نمودار نشان داده شده است.

Keywords:

مجموعه مستقل بیشینه , موازی سازی , ام پی آی , تئوری گراف