%0 Journal Article
%T Algorithms for Longest Path : A Survey<br>最长路径问题研究进展
%A WANG Jian-xin
%A YANG Zhi-biao
%A CHEN Jian-er
%A <br>王建新
%A 杨志彪
%A 陈建二
%J 计算机科学
%D 2009
%I 
%X The longest path problem is well-known NP-Hard, and has significant applications in many fields such as bioinformatics. After the emerging of parameterized computation theory, the parameterized k-Path problem becomes one of the most concerned research problems. We introduced several algorithms to solve the longest path problem, including approximate algorithms,parameterized algorithms and polynomial time algorithms on special graphs. We put emphasis on the analysis and comparison of the latest results in parameterized algorithm, which use color-coding, divide-and-conquer and algebra techniques to solve k-Path problem. At last, we presented some further research directions for this problem.
%K Longest path
%K k-Path problem
%K NP-hard
%K Parameterized computation<br>最长路径
%K k-Path问题
%K NP难
%K 参数计算
%U http://www.alljournals.cn/get_abstract_url.aspx?pcid=5B3AB970F71A803DEACDC0559115BFCF0A068CD97DD29835&cid=8240383F08CE46C8B05036380D75B607&jid=64A12D73428C8B8DBFB978D04DFEB3C1&aid=FD4FF861C58E63C95C2BB3BCA4EF81E5&yid=DE12191FBD62783C&vid=933658645952ED9F&iid=59906B3B2830C2C5&sid=CA4FD0336C81A37A&eid=E158A972A605785F&journal_id=1002-137X&journal_name=计算机科学&referenced_num=0&reference_num=36