最长路径问题研究进展

摘要：

最长路径问题是著名的NP难问题,在生物信息学等领域中有着重要的应用.参数计算理论产生后,参数化形式的k-Path问题成了研究的热点.介绍了现有求解最长路径问题的几种算法,包括近似算法、参数化算法和特殊图的多项式时间算法;着重分析和比较了参数化算法中利用着色、分治和代数法研究k-Path问题的最新结果.最后,提出了该问题的进一步研究方向.

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

所属期刊栏目：36

分类号：O15;O1

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

在线出版日期：2010-03-02（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：1-4,31