Iterative Expansion and Color Coding
Lists
Only you see this
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...