معین منعمی - دانشجوی کارشناسی ارشد الگوریتم و محاسبات ، دانشکدگان فنی دانشگاه تهران
فاطمه ولی پور - دانشجوی کارشناسی ارشد الگوریتم و محاسبات، دانشکدگان فنی دانشگاه تهران
روح اله عابدیان - استادیار دانشکده ی علوم مهندسی دانشگدگان فنی دانشگاه تهران

در این مقاله ، مسئله کمترین پوشش راسی یا Minimum Vertex Cover به عنوان یک مسئله کلاسیک بهینه سازی گراف با پیچیدگی NP-complete مورد بررسی قرار گرفته است . ما یک الگوریتم موثر با نامStrategic Approach Based On Degree Distribution in Minimum Vertex Cover Problem (SABOD) طراحی کردهایم تا کمترین پوشش گرههای یک گراف را بدست آوریم . عملکرد SABOD برروی تعداد زیادی از گرافهای تصادفی و گرافهای بنچمارک DIMACS, BHOSLIB و گرافهای واقعی مانند شبکه اجتماعی مورد آزمایش قرار گرفته و با سایر روشهای موجود مقایسه شده است . نتایج گستردهی شبیه سازی نشان می دهد که SABOD ممکن است راهحل های بهتری نسبت به الگوریتم های موجود برای حل مسئله کمترین پوشش گره ارائه دهد.

کمترین پوشش راسی ، SABOD، MDG، NOVCA، NP-complete