Iterative Expansion and Color Coding: An Improved Algorithm for 3D-Matching

作者：Chen Jianer^*; Liu Yang; Lu Songjian; Sze Sing Hoi; Zhang Fenghui

来源：ACM Transactions on Algorithms, 2012, 8(1): 6.

DOI：10.1145/2071379.2071385

• Color coding
• dynamic programming matching
• parameterized algorithms

The research in the parameterized 3D-MATCHING problem has yielded a number of new algorithmic techniques and an impressive list of improved algorithms. In this article, a new deterministic algorithm for the problem is developed that integrates and improves a number of known techniques, including greedy localization, dynamic programming, and color coding. The new algorithm, which either constructs a matching of k triples in a given triple set or correctly reports that no such a matching exists, runs in time O*(2.80(3k)), improving a long list of previous algorithms for the problem.

• 出版日期2012-1