@inbook{fc461bc4e7f64d458340b46baa2e1805,

title = "Faster fixed-parameter tractable algorithms for matching and packing problems",

abstract = "We obtain faster algorithms for problems such as r-dimensional matching, r-set packing, graph packing, and graph edge 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). Previously such a kernel was known only for triangle packing. This technique lets us combine, in a new and sophisticated way, Alon, Yuster and Zwick's color-coding technique with dynamic programming on the structure of the kernel to obtain faster fixed-parameter algorithms for these problems. Our algorithms run in time O(n + 2O(k)), an improvement over previous algorithms for some of these problems running in time O(n + kO(k)). The flexibility of our approach allows tuning of algorithms to obtain smaller constants in the exponent.",

author = "Fellows, {Michael R.} and C. Knauer and N. Nishimura and P. Ragde and F. Rosamond and U. Stege and Thilikos, {Dimitrios M.} and S. Whitesides",

year = "2004",

doi = "10.1007/978-3-540-30140-0_29",

language = "English (US)",

isbn = "3540230254",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "311--322",

editor = "Susanne Albers and Tomasz Radzik",

booktitle = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

}