2004 | OriginalPaper | Buchkapitel
Faster Fixed-Parameter Tractable Algorithms for Matching and Packing Problems
verfasst von : Michael R. Fellows, C. Knauer, N. Nishimura, P. Ragde, F. Rosamond, U. Stege, Dimitrios M. Thilikos, S. Whitesides
Erschienen in: Algorithms – ESA 2004
Verlag: Springer Berlin Heidelberg
Enthalten in: Professional Book Archive
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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.