Iterative Expansion and Color Coding: An Improved Algorithm for 3D-Matching Conference Paper uri icon

abstract

  • 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 3 k ), improving a long list of previous algorithms for the problem.

published proceedings

  • ACM TRANSACTIONS ON ALGORITHMS

author list (cited authors)

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

citation count

  • 12

complete list of authors

  • Chen, Jianer||Liu, Yang||Lu, Songjian||Sze, Sing-Hoi||Zhang, Fenghui

publication date

  • January 2012