کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6874673 | 1441188 | 2018 | 17 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Designing deterministic polynomial-space algorithms by color-coding multivariate polynomials
ترجمه فارسی عنوان
الگوریتم های فضای چند جملهای قطعی را با چند جمله ای چند متغیره رنگی طراحی می کند
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
We introduce an enhancement of color coding to design deterministic polynomial-space parameterized algorithms. Our approach aims at reducing the number of random choices by exploiting the special structure of a solution. Using our approach, we derive polynomial-space Oâ(3.86k)-time (exponential-space Oâ(3.41k)-time) deterministic algorithm for k-Internal Out-Branching, improving upon the previously fastest exponential-space Oâ(5.14k)-time algorithm for this problem. (The notation Oâ hides polynomial factors.) We also design polynomial-space Oâ((2e)k+o(k))-time (exponential-space Oâ(4.32k)-time) deterministic algorithms for k-ColorfulOut-Branching on arc-colored digraphs and k-Colorful Perfect Matching on planar edge-colored graphs. In k-Colorful Out-Branching, given an arc-colored digraph D, decide whether D has an out-branching with arcs of at least k colors. k-Colorful Perfect Matching is defined similarly. To obtain our polynomial-space algorithms, we show that (n,k,αk)-splitters (α⩾1) and in particular (n,k)-perfect hash families can be enumerated one by one with polynomial delay using polynomial space.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Computer and System Sciences - Volume 95, August 2018, Pages 69-85
Journal: Journal of Computer and System Sciences - Volume 95, August 2018, Pages 69-85
نویسندگان
Gregory Gutin, Felix Reidl, Magnus Wahlström, Meirav Zehavi,