کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4949497 | 1440192 | 2017 | 18 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Rerouting shortest paths in planar graphs
ترجمه فارسی عنوان
تغییر مسیر کوتاهترین مسیرها در نمودارهای مسطح
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
کوتاهترین مسیر، تغییر مسیر مشکل تصحیح نمودار پلانار، زمان چندجملهای، برنامه نویسی دینامیک،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
A rerouting sequence is a sequence of shortest st-paths such that consecutive paths differ in one vertex. We study the Shortest Path Rerouting Problem, which asks, given two shortest st-paths P and Q in a graph G, whether a rerouting sequence exists from P to Q. This problem is PSPACE-hard in general, but we show that it can be solved in polynomial time if G is planar. In addition, it can be solved in polynomial time when every vertex has at most two neighbors closer to s and at most two neighbors closer to t. To this end, we introduce a dynamic programming method for reconfiguration problems, based on using small encodings of reconfiguration graphs.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 231, 20 November 2017, Pages 95-112
Journal: Discrete Applied Mathematics - Volume 231, 20 November 2017, Pages 95-112
نویسندگان
Paul Bonsma,