Narrow sieves for parameterized paths and packings
Loading...
Access rights
openAccess
URL
Journal Title
Journal ISSN
Volume Title
A1 Alkuperäisartikkeli tieteellisessä aikakauslehdessä
This publication is imported from Aalto University research portal.
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
Other link related to publication (opens in new window)
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
Other link related to publication (opens in new window)
Date
2017
Department
Major/Subject
Mcode
Degree programme
Language
en
Pages
119–139
Series
JOURNAL OF COMPUTER AND SYSTEM SCIENCES, Volume 87
Abstract
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.Description
Keywords
Determinant, Edge coloring, Graph algorithm, k-Path, Multidimensional matching, Polynomial identity testing, Randomized algorithm, Set packing, Sieve
Other note
Citation
Björklund, A, Husfeldt, T, Kaski, P & Koivisto, M 2017, ' Narrow sieves for parameterized paths and packings ', Journal of Computer and System Sciences, vol. 87, pp. 119–139 . https://doi.org/10.1016/j.jcss.2017.03.003