کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4949501 | 1440192 | 2017 | 16 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
The shortest connection game
ترجمه فارسی عنوان
کوتاهترین بازی اتصال
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
کوتاهترین مشکل مسیر نظریه بازی، پیچیدگی محاسباتی، نمودار کاکتوس،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
In this work we analyse the computational complexity of Shortest Connection Game. On the negative side, Shortest Connection Game turns out to be computationally hard even on restricted graph classes such as bipartite, acyclic and cactus graphs. On the positive side, we can give a polynomial time algorithm for cactus graphs when the game is restricted to simple paths.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 231, 20 November 2017, Pages 139-154
Journal: Discrete Applied Mathematics - Volume 231, 20 November 2017, Pages 139-154
نویسندگان
Andreas Darmann, Ulrich Pferschy, Joachim Schauer,