The longest cycle problem is polynomial on interval graphs
The longest cycle problem is polynomial on interval graphs
复制标题
最长循环问题是区间图上的多项式
DOI：
10.1016/j.tcs.2021.01.005
复制
发表时间：
2021
影响因子：
1.1
通讯作者：
石艺
中科院分区：
文献类型：
--
作者：
尚建辉;李鹏;石艺
最长循环问题是在图中找到具有最大顶点的循环的问题。尽管它可以在少数平凡图类上以多项式时间求解，但最长循环问题众所周知是 NP 完全问题。为了解决最长周期问题，人们付出了很多努力。然而，据我们所知，没有多项式算法可以解决任何非平凡的图类。区间图是弦图和星体三自由图的交集，被认为是具有最长周期问题多项式算法的非试验图类。 2009 年，K. Ioannidou, G.B. Mertzios 和 S.D. Nikolopoulos 在 Ioannidou 等人中提出了一种用于区间图最长路径问题的多项式算法。 （2009）[19]。受他们工作的启发，我们研究了区间图的最长循环问题。在本文中，我们提出了第一个用于区间图最长循环问题的多项式算法。在运行时间为 O(n8) 的多项式算法中提出了动态规划方法，其中 n 是输入图的顶点数。使用类似的方法，我们设计了一种多项式算法来解决区间图上最长的 k 厚子图问题，这将在另一项单独的工作中介绍。根据我们发现的 k 厚区间图的有趣性质（例如，当且仅当 G 为 1 厚时，区间图 G 是可追踪的；当且仅当 G 为 2 厚时，G 是哈密顿连通的；当且仅当 G 是 3 厚时，G 是哈密顿连通的，等等），本文提出的算法对于研究区间图上的跨越连通性非常重要。
The longest cycle problem is the problem of finding a cycle with maximal vertices in a graph. Although it is solvable in polynomial time on few trivial graph classes, the longest cycle problem is well known as NP-complete. A lot of efforts have been devoted to the longest cycle problem. To the best of our knowledge however, there are no polynomial algorithms that can solve any of the non-trivial graph classes. Interval graphs, the intersection of chordal graphs and asteroidal triple-free graphs, are known to be the non-trial graph classes that have polynomial algorithm of the longest cycle problem. In 2009, K. Ioannidou, G.B. Mertzios and S.D. Nikolopoulos presented a polynomial algorithm for the longest path problem on interval graphs in Ioannidou et al. (2009) [19]. Inspired by their work, we investigate the longest cycle problem of interval graphs. In this paper, we present the first polynomial algorithm for the longest cycle problem on interval graphs. A dynamic programming approach is proposed in the polynomial algorithm that runs in O(n8) time, where n is the number of vertices of the input graph. Using a similar approach, we design a polynomial algorithm to solve the longest k-thick subgraph problem on interval graphs which will be presented in another separate work. According to the interesting properties of k-thick interval graphs that we discovered (e.g., an interval graph G is traceable if and only if G is 1-thick, G is hamiltonian if and only if G is 2-thick, G is hamiltonian connected if and only if G is 3-thick and so on), the algorithm presented in this paper can be important in studying the spanning connectivity on interval graphs.
登录
查看更多内容
DOI：
10.1137/130910658
发表时间：
2013-02
期刊：
ArXiv
影响因子：
--
作者：
D. Rautenbach;Jean-Sébastien Sereni
通讯作者：
D. Rautenbach;Jean-Sébastien Sereni
图最长循环中的大度数顶点，I
DOI：
10.7151/dmgt.1861
发表时间：
2016
期刊：
Discussiones Mathematicae - Graph Theory
影响因子：
--
作者：
Li Binlong;Xiong Liming;Yin Jun
通讯作者：
Yin Jun
DOI：
--
发表时间：
2013
期刊：
Ars Comb.
影响因子：
--
作者：
Minko Markov;T. Vassilev;Krassimir Manev
通讯作者：
Minko Markov;T. Vassilev;Krassimir Manev
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
影响因子：
1.1
作者：
Ioannidou, Kyriaki;Mertzios, George B.;Nikolopoulos, Stavros D.
通讯作者：
Nikolopoulos, Stavros D.