|
عنوان
|
مساله طولانیترین مسیر توسعهیافته در حالت حذف کمانها
|
|
نوع پژوهش
|
مقاله ارائه شده کنفرانسی
|
|
کلیدواژه‌ها
|
تحقیق در عملیات، شبکه های جریان
|
|
چکیده
|
در این مقاله، براساس تعریف بیان شده در [ 13 ]، مساله طولانیترین مسیر توسعه یافته در شبکه های فاقد دور مورد بررسی قرار میگیرد. ابتدا مساله طولانیترین مسیر توسع هیافته برای حالت حذف حداکثر k کمان را تعریف کرده و ثابت می کنیم اگر k=1، آنگاه میتوان مساله را در زمان چندجملهای حل کرد و اگر k\geq2، آنگاه مساله NP-Complete است.
|
|
پژوهشگران
|
مهدی قیاسوند (نفر اول)، فائزه زهره وند (نفر دوم)
|