Abstract
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.
Original language | English (US) |
---|---|
Pages (from-to) | 167-176 |
Number of pages | 10 |
Journal | Algorithmica (New York) |
Volume | 52 |
Issue number | 2 |
DOIs | |
State | Published - Oct 2008 |
Keywords
- Color coding
- Fixed parameter tractable
- Graph matching
- Parameterized complexity
- Set packing
ASJC Scopus subject areas
- General Computer Science
- Computer Science Applications
- Applied Mathematics