| 最长路径问题研究进展 |
| |
| 引用本文： | 王建新,杨志彪,陈建二.最长路径问题研究进展[J].计算机科学,2009,36(12):1-4. |
| |
| 作者姓名： | 王建新 杨志彪 陈建二 |
| |
| 作者单位： | 中南大学信息科学与工程学院,长沙,410083 |
| |
| 基金项目： | 国家自然科学基金，国家973前期研究专项，湖南省杰出青年基金，新世纪优秀人才支持计划，国家教育部创新团队资助计划 |
| |
| 摘 要： | 最长路径问题是著名的NP难问题,在生物信息学等领域中有着重要的应用.参数计算理论产生后,参数化形式的k-Path问题成了研究的热点.介绍了现有求解最长路径问题的几种算法,包括近似算法、参数化算法和特殊图的多项式时间算法;着重分析和比较了参数化算法中利用着色、分治和代数法研究k-Path问题的最新结果.最后,提出了该问题的进一步研究方向.
|
| 关 键 词： | 最长路径 k-Path问题 NP难 参数计算 |
| 收稿时间： | 2009/1/13 0:00:00 |
| 修稿时间： | 2009/3/16 0:00:00 |
Algorithms for Longest Path : A Survey |
| |
| WANG Jian-xin,YANG Zhi-biao,CHEN Jian-er.Algorithms for Longest Path : A Survey[J].Computer Science,2009,36(12):1-4. |
| |
| Authors: | WANG Jian-xin YANG Zhi-biao CHEN Jian-er |
| |
| Affiliation: | (School of Information Science and Engineering,Central South University,Changsha 410083,China) |
| |
| Abstract: | 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. |
| |
| Keywords: | Longest path k-Path problem NP-hard Parameterized computation |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
| 点击此处可从《计算机科学》浏览原始摘要信息 |
|
点击此处可从《计算机科学》下载全文 |
|
