Finding Hamiltonian paths in cocomparability graphs using the bump number algorithm

Peter Damaschke, Jitender S. Deogun, Dieter Kratsch, George Steiner

Research output: Contribution to journalArticlepeer-review

34 Scopus citations


Hamiltonian Path/Cycle are well known NP-complete problems on general graphs, but their complexity status for permutation graphs has been an open question in algorithmic graph theory for many years. In this paper, we prove that the Hamiltonian Path problem is solvable in polynomial time even for the larger class of cocomparability graphs. Our result is based on a nice relationship between Hamiltonian paths and the bump number of partial orders. As another consequence we get a new interpretation of the bump number in terms of path partitions, leading to polynomial time solutions of the Hamiltonian Path/Cycle Completion problems in cocomparability graphs.

Original languageEnglish (US)
Pages (from-to)383-391
Number of pages9
Issue number4
StatePublished - Dec 1991


  • Hamiltonian paths and cycles
  • Mathematics Subject Classification (1991): 05C45
  • bump number
  • cocomparability graphs
  • partial orders

ASJC Scopus subject areas

  • Algebra and Number Theory
  • Geometry and Topology
  • Computational Theory and Mathematics


Dive into the research topics of 'Finding Hamiltonian paths in cocomparability graphs using the bump number algorithm'. Together they form a unique fingerprint.

Cite this