The Longest Path Problem Is Polynomial on Interval Graphs
The Longest Path Problem Is Polynomial on Interval Graphs
复制标题
DOI：
10.1007/978-3-642-03816-7_35
复制
发表时间：
2009-08
期刊：
影响因子：
--
通讯作者：
Kyriaki Ioannidou;G. B. Mertzios;Stavros D. Nikolopoulos
中科院分区：
文献类型：
--
作者：
Kyriaki Ioannidou;G. B. Mertzios;Stavros D. Nikolopoulos
最长路问题是在一个图中寻找一条最长的路的问题。这个问题的多项式解只在少数几类图中存在，而在一般图中它是NP困难的，因为它是哈密顿路径问题的推广。受Uehara和Uno在[20]中的工作的启发，他们留下了区间图类的最长路问题，在本文中，我们证明了这个问题可以在多项式时间内解决。该算法的时间复杂度为O（n4），其中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 in [20], 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 runs inO(n4) time, wherenis the number of vertices of the input graph, and bases on a dynamic programming approach.