An Algorithm for 3-Dimensional Matching Problem Based on Color Coding and Dynamic Programming
一个基于着色和动态规划的3-维匹配问题算法

3-Dimensional Matching is one of the six classic NP-complete problems, which has extensive application in scheduling, assignment, transportation and network flow problem, etc. Parameterized computation theory is a recently developed new method to study and solve NP-hard problems. At the present, for the 3-Dimensional Matching problem, the best result of deterministic parameterized algorithm is O(163k. This paper combines color coding and dynamic programming, and presents a deterministic parameterized algorithm of running time O(3.423k, which significantly improves the previous best deterministic algorithm.