最长路径问题研究进展  

Algorithms for Longest Path:A Survey

作　　者：王建新[1] 杨志彪[1] 陈建二[1] 

机构地区：[1]中南大学信息科学与工程学院,长沙410083

出　　处：《计算机科学》2009年第12期1-4,31,共5页Computer Science

基　　金：国家自然科学基金(60773111);国家973前期研究专项(2008CB317107);湖南省杰出青年基金(06JJ10009);新世纪优秀人才支持计划(NCET-O5-0683);国家教育部创新团队资助计划(IRT0661)资助

摘　　要：最长路径问题是著名的NP难问题,在生物信息学等领域中有着重要的应用。参数计算理论产生后,参数化形式的k-Path问题成了研究的热点。介绍了现有求解最长路径问题的几种算法,包括近似算法、参数化算法和特殊图的多项式时间算法;着重分析和比较了参数化算法中利用着色、分治和代数法研究k-Path问题的最新结果。最后,提出了该问题的进一步研究方向。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-con-quer and algebra techniques to solve k-Path problem. At last, we presented some further research directions for this problem.

关 键 词：最长路径 k-Path问题 NP难 参数计算 

分 类 号：TP311.1[自动化与计算机技术—计算机软件与理论] O157.5[自动化与计算机技术—计算机科学与技术]