کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6875963 | 689638 | 2016 | 13 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Parameterized certificate dispersal and its variants
ترجمه فارسی عنوان
پراکندگی گواهی پارامتری و انواع آن
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
Although polynomial-time solvable for constant values of k, the former variant seems much harder, surfacing in the proof that it is W[1]-hard with respect to k while ChainedMinimum Certificate Dispersal yields a polynomial-size problem kernel. We even show fixed-parameter tractability of the latter with respect to the stronger parameter “number t of terminals”. In particular, while there is no polynomial-size kernel with respect to t, the problem admits a polynomial-size Turing kernel. Towards answering the question whether Minimum Certificate Dispersal can be solved in polynomial time when t is constant, we show polynomial-time solvability for at most two requests (comprising all instances with tâ¤2) using an algorithm for the Strong Distance problem, which asks for a minimum-size subdigraph in which two given vertices are strongly connected. Finally, we emphasize the hardness of Minimum Certificate Dispersal by proving it NP-hard for very restricted sets of instances, thereby excluding many parameters and combinations from consideration for efficient multivariate algorithms.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 622, 4 April 2016, Pages 66-78
Journal: Theoretical Computer Science - Volume 622, 4 April 2016, Pages 66-78
نویسندگان
Valentin Garnero, Mathias Weller,