POLYNOMIAL ALGORITHMS FOR HAMILTONIAN CYCLE IN COCOMPARABILITY GRAPHS
POLYNOMIAL ALGORITHMS FOR HAMILTONIAN CYCLE IN COCOMPARABILITY GRAPHS
复制标题
DOI：
10.1137/s0097539791200375
复制
发表时间：
1994-06-01
影响因子：
1.6
通讯作者：
STEINER, G
中科院分区：
文献类型：
--
作者：
DEOGUN, JS;STEINER, G
在图中求哈密顿环是一个经典的np完全问题。排列图中哈密顿问题的复杂性是一个众所周知的开放问题。本文解决了一类更一般的共比较图的哈密顿问题的复杂性。证明了共比较图的哈密顿循环存在性问题是在p中存在的，并给出了构造哈密顿路径和循环的多项式时间算法。该方法利用了可比较图中的哈密顿问题与其互补图的传递方向对应的偏阶凹凸数问题之间的关系。
Finding a Hamiltonian cycle in a graph is one of the classical NP-complete problems. Complexity of the Hamiltonian problem in permutation graphs has been a well-known open problem. In this paper the authors settle the complexity of the Hamiltonian problem in the more general class of cocomparability graphs. It is shown that the Hamiltonian cycle existence problem for cocomparability graphs is in P. A polynomial time algorithm for constructing a Hamiltonian path and cycle is also presented. The approach is based on exploiting the relationship between the Hamiltonian problem in a cocomparability graph and the bump number problem in a partial order corresponding to the transitive orientation of its complementary graph.