Hamiltonian cycle is polynomial on cocomparability graphs

DOI10.1016/0166-218X(92)90168-AzbMath0772.05064OpenAlexW2001405099MaRDI QIDQ1201106

George Steiner, Jitender S. Deogun

Publication date: 17 January 1993

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0166-218x(92)90168-a

zbMATH Keywords

polynomial time algorithmHamiltonian cyclepartial orderHamilton pathcocomparability graphsbump number

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Eulerian and Hamiltonian graphs (05C45)

Related Items

The path-partition problem in block graphs, Hamiltonian paths, unit-interval complexes, and determinantal facet ideals, Weighted domination of cocomparability graphs, Finding Hamiltonian paths in cocomparability graphs using the bump number algorithm, Hamiltonian cycle is polynomial on cocomparability graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Finding Hamiltonian circuits in interval graphs
• A combinatorial bijection between linear extensions of equivalent orders
• Computing the bump number is easy
• Computing the bump number with techniques from two-processor scheduling
• Finding Hamiltonian paths in cocomparability graphs using the bump number algorithm
• Hamiltonian cycle is polynomial on cocomparability graphs
• The NP-completeness column: an ongoing guide
• Two-Processor Scheduling with Start-Times and Deadlines
• Hamilton Paths in Grid Graphs