الگوریتم تقریبی برای مسئله حداقل پوشش راسی با رویکرد استراتژیک مبتنی بر توزیع درجات

در این مقاله ، مسئله کمترین پوشش راسی یا 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