本项目主要工作是区间图的三个算法问题：第一是固定两个端点的汉密尔顿路问题，第二是最长圈和最长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树的复杂数据结构，我们给出了区间图线性认证算法，不利用任何复杂数据结构。最主要的是第一个工作。

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.