Greedy localization and color-coding: Improved matching and packing algorithms Conference Paper uri icon

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.

author list (cited authors)

  • Liu, Y., Lu, S., Chen, J., & Sze, S.

publication date

  • January 2006