کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4951226 | 1441196 | 2017 | 21 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Narrow sieves for parameterized paths and packings
ترجمه فارسی عنوان
ستون های باریک برای مسیرها و بسته بندی های پارامتریک
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
We present parameterized algorithms for the k-path problem, the p-packing of q-sets problem, and the q-dimensional p-matching problem. Our algorithms solve these problems with high probability in time exponential only in the parameter (k, p, q) and using polynomial space. The constant bases of the exponentials are significantly smaller than in previous works; for example, for the k-path problem the improvement is from 2 to 1.66. We also show how to detect if a d-regular graph admits an edge coloring with d colors in time within a polynomial factor of 2(dâ1)n/2. Our techniques generalize an algebraic approach studied in various recent works.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Computer and System Sciences - Volume 87, August 2017, Pages 119-139
Journal: Journal of Computer and System Sciences - Volume 87, August 2017, Pages 119-139
نویسندگان
Andreas Björklund, Thore Husfeldt, Petteri Kaski, Mikko Koivisto,