سعیده محمد بیگی فرد - دانشگاه آزاد اسلامی واحد کرج
مجید زهره بندیان - دانشگاه آزاد اسلامی واحد کرج

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

مسیله مینیمم پوشش راسی، الگوریتم حل مسیله پوشش راسی ، زمان چندجمله ای