کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4951282 | 1364339 | 2017 | 11 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Rural postman parameterized by the number of components of required edges
ترجمه فارسی عنوان
پستچی روستایی با تعدادی از اجزای لبه های مورد نیاز پارامتر می شود
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
پارامتر ثابت قابل ردیابی مشکل پستچی روستایی، الگوریتم های تصادفی،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
In the Directed Rural Postman Problem (DRPP), given a strongly connected directed multigraph D=(V,A) with nonnegative integral weights on the arcs, a subset R of required arcs and a nonnegative integer â, decide whether D has a closed directed walk containing every arc of R and of weight at most â. Let k be the number of weakly connected components in the subgraph of D induced by R. Sorge et al. [30] asked whether the DRPP is fixed-parameter tractable (FPT) when parameterized by k, i.e., whether there is an algorithm of running time Oâ(f(k)) where f is a function of k only and the Oâ notation suppresses polynomial factors. Using an algebraic approach, we prove that DRPP has a randomized algorithm of running time Oâ(2k) when â is bounded by a polynomial in the number of vertices in D. The same result holds for the undirected version of DRPP.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Computer and System Sciences - Volume 83, Issue 1, February 2017, Pages 121-131
Journal: Journal of Computer and System Sciences - Volume 83, Issue 1, February 2017, Pages 121-131
نویسندگان
Gregory Gutin, Magnus Wahlström, Anders Yeo,