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 language | English (US) |
---|---|
Pages (from-to) | 383-391 |
Number of pages | 9 |
Journal | Order |
Volume | 8 |
Issue number | 4 |
DOIs | |
State | Published - Dec 1991 |
Externally published | Yes |
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