Polynomial algorithms for Hamiltonian cycle in cocomparability graphs

Jitender S. Deogun, George Steiner

Research output: Contribution to journalArticlepeer-review

50 Scopus citations


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.

Original languageEnglish (US)
Pages (from-to)520-552
Number of pages33
JournalSIAM Journal on Computing
Issue number3
StatePublished - 1994

ASJC Scopus subject areas

  • General Computer Science
  • General Mathematics


Dive into the research topics of 'Polynomial algorithms for Hamiltonian cycle in cocomparability graphs'. Together they form a unique fingerprint.

Cite this