%0 Journal Article
%T An Algorithm for 3-Dimensional Matching Problem Based on Color Coding and Dynamic Programming<br>一个基于着色和动态规划的3-维匹配问题算法
%A NING Dan
%A WANG Jian-Xin
%A <br>宁丹
%A 王建新
%J 计算机科学
%D 2007
%I 
%X 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.
%K 3-Dimensional matching
%K Color coding
%K Dynamic programming<br>3-维匹配
%K 着色
%K 动态规划
%U http://www.alljournals.cn/get_abstract_url.aspx?pcid=5B3AB970F71A803DEACDC0559115BFCF0A068CD97DD29835&cid=8240383F08CE46C8B05036380D75B607&jid=64A12D73428C8B8DBFB978D04DFEB3C1&aid=1E8759907DE65478D54C22406562CA95&yid=A732AF04DDA03BB3&vid=339D79302DF62549&iid=DF92D298D3FF1E6E&sid=8B59EA573021D671&eid=A1266CF37D675CF1&journal_id=1002-137X&journal_name=计算机科学&referenced_num=0&reference_num=13