کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4949854 1364260 2017 16 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
On the Shortest Path Game
ترجمه فارسی عنوان
در کوتاهترین مسیر بازی
کلمات کلیدی
کوتاهترین مشکل مسیر نظریه بازی، پیچیدگی محاسباتی، نمودار کاکتوس،
ترجمه چکیده
از سوی دیگر، ما می توانیم الگوریتم های زمان چندجملهای برای نمودارهای تصادفی هدایت شده و برای نمودارهای کاکتوس حتی در مورد بدون هدایت ارائه دهیم. دومی بر اساس تجزیه گراف به اجزای سازنده و حل آنها توسط تعدادی از آرایه های برنامه ریزی پویا درگیر است. در نهایت، ما برخی از استدلال ها را در مورد تعطیلی شکاف وضعیت پیچیدگی برای نمودارهایی از عرض درخت محدود می کنیم.
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش مقاله
در کوتاهترین مسیر بازی
چکیده انگلیسی
On the other hand, we can give polynomial time algorithms for directed acyclic graphs and for cactus graphs even in the undirected case. The latter is based on a decomposition of the graph into components and their resolution by a number of fairly involved dynamic programming arrays. Finally, we give some arguments about closing the gap of the complexity status for graphs of bounded treewidth.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 217, Part 1, 30 January 2017, Pages 3-18
نویسندگان
, , ,