Polynomial algorithms for Hamiltonian cycle in cocomparability graphs

Jitender S. Deogun, George Steiner

Research output: Contribution to journalArticlepeer-review

39 Scopus citations

Abstract

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
Volume23
Issue number3
DOIs
StatePublished - 1994

ASJC Scopus subject areas

  • Computer Science(all)
  • Mathematics(all)

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

Cite this