الگوريتم جديد براي مساله پوشش ٣-مسير

در مساله پوششk مسير، هدف تعيين مجموعه اي از راسها است به طوري كه هر مسير با طولK حداقل يكراس در اين مجموعه داشته باشد. در حالتي كه ٢ =K باشد، مساله، به مساله پوشش تبديل مي شود. اين مسالهمانند مساله پوشش،Np تام است. ما در اين مقاله الگوريتمي ابتكاري با مرتبه زماني $(O^3(n$ براي مساله ٣-پوشش ارائه مي دهيم كه براي هر گراف داده شده، يك ٣-پوشش با اندازه كوچك تعيين مي كند.