Please use this identifier to cite or link to this item: http://hdl.handle.net/1959.13/41262

OpenURL Link
Title
Faster fixed-parameter tractable algorithms for matching and packing problems
Author/Creator
Fellows, M. R.;  Knauer, C.;  Nishimura, N.;  Ragde, P.;  Rosamond, F.;  Stege, U.;  Thilikos, D. M.;  Whitesides, S.
Institution
The University of Newcastle. Research Division, Office of the Deputy Vice-Chancellor (Research)
Description
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.
Relation
Algorithmica Vol. 52, Issue 2, p. 167-176
Publisher Link
http://dx.doi.org/10.1007/s00453-007-9146-y
Date
2008
Publisher
Springer
Keyword(s)
parameterized complexity;  fixed parameter tractable;  graph matching;  set packing;  color coding
Resource Type
journal article
Identifier
http://hdl.handle.net/1959.13/41262
Identifier
ISSN:1432-0541
Reviewed
Reviewed
19 Visitors 20 Hits 0 Downloads
Save/E-mail Citation
Citation Format
E-mail Address
Subject
"Algorithmica"
 
OR