Narrow sieves for parameterized paths and packings

Show full item record



Permalink

http://hdl.handle.net/10138/288208

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

Title: Narrow sieves for parameterized paths and packings
Author: Björklund, Andreas; Husfeldt, Thore; Kaski, Petteri; Koivisto, Mikko
Other contributor: University of Helsinki, Aalto University
University of Helsinki, Department of Computer Science

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
Rights:


Files in this item

Total number of downloads: Loading...

Files Size Format View
JCSS_2017.pdf 412.7Kb PDF View/Open

This item appears in the following Collection(s)

Show full item record