Greedy localization and color-coding: Improved matching and packing algorithms
Conference Paper
Overview
Identity
Additional Document Info
View All
Overview
abstract
Matching and packing problems have formed an important class of NP-hard problems. There have been a number of recently developed techniques for parameterized algorithms for these problems, including greedy localization, color-coding plus dynamic programming, and randomized divide-and-conquer. In this paper, we provide further theoretical study on the structures of these problems, and develop improved algorithmic methods that combine existing and new techniques to obtain improved algorithms for matching and packing problems. For the 3-SET PACKING problem, we present a deterministic algorithm of time O*(4.613k), which significantly improves the previous best deterministic algorithm of time O* (12.83k). For the 3-D MATCHING problem, we develop a new randomized algorithm of running time O*(2.323k) and a new deterministic algorithm of running time O* (2.7733k). Our randomized algorithm improves the previous best randomized algorithm of running time O*(2.523k), and our deterministic algorithm significantly improves the previous best deterministic algorithm of running time O*(12.83k). Our results also imply improved algorithms for various triangle packing problems in graphs. Springer-Verlag Berlin Heidelberg 2006.
name of conference
Parameterized and Exact Computation, Second International Workshop, IWPEC 2006, Zrich, Switzerland, September 13-15, 2006, Proceedings
Parameterized and Exact Computation, Second International Workshop, IWPEC 2006, Zürich, Switzerland, September 13-15, 2006, Proceedings