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

37 Scopus citations

Abstract

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
JournalOrder
Volume8
Issue number4
DOIs
StatePublished - Dec 1991
Externally publishedYes

Keywords

  • 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

Fingerprint

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