Iterative Expansion and Color Coding

Jianer Chen, Yang Liu, Songjian Lu, Sing‐Hoi Sze, Fenghui ZhangACM Transactions on Algorithms 2012 · DOI

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.
BibTeX
@article{chen2012iterative,
  author = {Jianer Chen and Yang Liu and Songjian Lu and Sing‐Hoi Sze and Fenghui Zhang},
  title = {{Iterative Expansion and Color Coding}},
  journal = {ACM Transactions on Algorithms},
  year = {2012},
  doi = {10.1145/2071379.2071385},
}

Loading related content...

Figure