The Longest Path Problem has a Polynomial Solution on Interval Graphs
The Longest Path Problem has a Polynomial Solution on Interval Graphs
复制标题
DOI：
10.1007/s00453-010-9411-3
复制
发表时间：
2011-10-01
期刊：
影响因子：
1.1
通讯作者：
Nikolopoulos, Stavros D.
中科院分区：
文献类型：
--
作者：
Ioannidou, Kyriaki;Mertzios, George B.;Nikolopoulos, Stavros D.
最长路问题是在一个图中寻找一条最长的路的问题。这个问题的多项式解只在少数几类图中存在，而在一般图中它是NP困难的，因为它是哈密顿路径问题的推广。受Uehara和Uno工作的启发（第15届国际研讨会论文集）。算法和计算（ISAAC），LNCS，第3341卷，第3341页。871-883，2004），其中，他们离开了最长路径问题开放的类的区间图，在本文中，我们表明，该问题可以解决在多项式时间的区间图。该算法使用动态规划方法，运行时间为O（n（4）），其中n是输入图的顶点数。
The longest path problem is the problem of finding a path of maximum length in a graph. Polynomial solutions for this problem are known only for small classes of graphs, while it is NP-hard on general graphs, as it is a generalization of the Hamiltonian path problem. Motivated by the work of Uehara and Uno (Proc. of the 15th Annual International Symp. on Algorithms and Computation (ISAAC), LNCS, vol. 3341, pp. 871-883, 2004), where they left the longest path problem open for the class of interval graphs, in this paper we show that the problem can be solved in polynomial time on interval graphs. The proposed algorithm uses a dynamic programming approach and runs in O(n (4)) time, where n is the number of vertices of the input graph.