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
Title: | Narrow sieves for parameterized paths and packings |
Author: | Björklund, Andreas; Husfeldt, Thore; Kaski, Petteri; Koivisto, Mikko |
Contributor organization: | Department of Computer Science Helsinki Institute for Information Technology |
Date: | 2017-08 |
Language: | eng |
Number of pages: | 21 |
Belongs to series: | Journal of Computer and System Sciences |
ISSN: | 0022-0000 |
DOI: | https://doi.org/10.1016/j.jcss.2017.03.003 |
URI: | http://hdl.handle.net/10138/288208 |
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. (c) 2017 Elsevier Inc. All rights reserved. |
Subject: |
Determinant Edge coloring
Graph algorithm k-Path Multidimensional matching Sieve Set packing Polynomial identity testing Randomized algorithm DISJOINT TRIANGLES NP-COMPLETENESS SET PACKING ALGORITHMS COLOR COMPLEXITY GRAPH TIME 113 Computer and information sciences |
Peer reviewed: | Yes |
Rights: | unspecified |
Usage restriction: | openAccess |
Self-archived version: | acceptedVersion |
Total number of downloads: Loading...
Files | Size | Format | View |
---|---|---|---|
JCSS_2017.pdf | 412.7Kb |
View/ |