Faster Fixed-Parameter Tractable Algorithms for Matching and Packing Problems

Autor:	Christian Knauer, Sue Whitesides, Frances A. Rosamond, Ulrike Stege, Dimitrios M. Thilikos, Michael R. Fellows, Naomi Nishimura, Prabhakar Ragde
Rok vydání:	2007
Předmět:	Dynamic programming Packing problems Polynomial General Computer Science Computational complexity theory Set packing Matching (graph theory) Applied Mathematics Color-coding Parameterized complexity Algorithm Computer Science Applications Mathematics
Zdroj:	Algorithmica. 52:167-176
ISSN:	1432-0541 0178-4617
DOI:	10.1007/s00453-007-9146-y
Popis:	We obtain faster algorithms for problems such as r-dimensional matching and r-set packing when the size k of the solution is considered a parameter. We first establish a general framework for finding and exploiting small problem kernels (of size polynomial in k). This technique lets us combine Alon, Yuster and Zwick’s color-coding technique with dynamic programming to obtain faster fixed-parameter algorithms for these problems. Our algorithms run in time O(n+2 O(k)), an improvement over previous algorithms for some of these problems running in time O(n+k O(k)). The flexibility of our approach allows tuning of algorithms to obtain smaller constants in the exponent.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::bca6c571270bb042442b5aeb88fe32cb https://doi.org/10.1007/s00453-007-9146-y Zobrazit plný text záznamu Full text from SpringerLink