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