区间图若干算法问题的研究

The main work of us is three algorithms of interval graphs. The first is the 2-fixed-endpoint Hamiltonian path (2HP) problem, the second is the longest cycle and longest k-thick subgraph, the third is a linear time certifying algorithm of interval graphs..(i) For interval graphs, the HP problem, and in general the path cover problem , possess very simple linear time algorithms. In 1993, Damaschke asked whether there exist polynomial time algorithms for solving the 1HP problem and the 2HP problem on interval graphs. In 2010, Asdre and Nikolopoulos proposed an O(|V (G)| 3 ) time algorithm for solving the 1PC problem on interval graph G. The main objective of our 2017 paper is to establish a linear time algorithm for solving the 1PC problem on any interval graph G. We already have a polynomial time algorithm for solving the general 2HP problem on interval graphs, which use the linear time algorithm for solving the interval graph 1HP problem as a subprogram and heavily rely on the mathematical observations developed in our 2017 paper..(ii)There are polynomial algorithms for the longest path problem on Ptolemaic graphs, interval graphs, cocomparability graphs, 2-Trees and circular-arc graphs. There are only a few results about the longest cycle problem. Seems that we only know Takahara et al. found a polynomial algorithm for the longest cycle problem on Ptolemaic graphs. We find a polynomial algorithm for the longest cycle and longest k-thick subgraph of interval graphs..(iii)Till now, seems that the only known linear time certifying recognition algorithm for interval graphs is reported by Kratsch et al.. This algorithm makes use of the recognition algorithm of Korte and M?hring, which in turn applies the data structure called MPQ tree. We mention that, after adding an additional certifying step, our 4-sweep LBFS interval graph recognition algorithm can be further developed into a certifying algorithm without any usage of a data structure like MPQ tree.

本项目主要工作是区间图的三个算法问题：第一是固定两个端点的汉密尔顿路问题，第二是最长圈和最长k-thick子图问题，第3个是线性认证算法。（1）1993年Damaschke提问区间图的HP、2HP问题是否有多项式算法。2010年，Asdre和Nikolopoulos得到区间图1PC/1HP问题的3次方算法。我们2017年给出了这个问题的线性算法，并利用它和发现的区间图相关结构性质得到了区间图2HP问题的多项式算法。（2）cocomparability、circular-arc等图类都存在最长路问题的多项式算法，而最长圈则只有Takahara 等人发现的Ptolemaic图类上有多项式算法。我们给出了区间图最长圈和最长k-thick子图的多项式算法。（3）区间图的认证算法只有Kratsch等人给出的利用MPQ树的复杂数据结构，我们给出了区间图线性认证算法，不利用任何复杂数据结构。最主要的是第一个工作。

本项目主要研究区间图的算法问题，第一是固定两个端点的汉密尔顿路问题，第二是最长圈和最长k-thick子图问题，第三个是区间图的线性认证算法。.（1）1993年Damaschke提问区间图的HP、2HP问题是否有多项式算法。2010年，Asdre和Nikolopoulos得到区间图1PC/1HP问题的3次方算法。我们2017年给出了这个问题的线性算法，并利用它和发现的区间图相关结构性质得到了区间图2HP问题的多项式算法。在2020年我们完成了这个问题的研究工作，但是还没来得及写成文章，因为这篇文章很长，预计还需要2年才能完成写作工作。.（2）cocomparability、circular-arc等图类都存在最长 路问题的多项式算法，而最长圈则只有Takahara 等人发现的Ptolemaic图类上有多项式算法。我们给出了区间图最长圈和最长k-thick子图的多项式算法。我们完成了这个问题的研究工作，并把文章投到了期刊Theoretical Computer Science，计算机领域一个非常不错的期刊。这篇文章于2021年1月2日被接收，将于2021年3月6日正式发表。.（3）区间图的认证算法只有Kratsch等人给出的利用MPQ数的复杂数据结构，我们给出了区间图线性认证算法，不利用任何复杂数据结构。我们完成了这个工作的研究和写作，并把文章投到了期刊 Algorithm，目前在审稿之中。