Finding Hamiltonian paths in cocomparability graphs using the bump number algorithm

DOI10.1007/BF00571188zbMath0760.05063OpenAlexW2089894925MaRDI QIDQ1198484

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

Publication date: 16 January 1993

Published in: Order (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf00571188

zbMATH Keywords

cyclepathpartial orderpermutation graphscocomparability graphbump number algorithmHamiltonian Path problem

Mathematics Subject Classification ID

Eulerian and Hamiltonian graphs (05C45)

Related Items

Cyclability in graph classes, The Longest Path Problem Is Polynomial on Interval Graphs, 1-tough cocomparability graphs are hamiltonian, Toughness, hamiltonicity and split graphs, Weighted domination of cocomparability graphs, HAMILTONian circuits in chordal bipartite graphs, Parameterizing path partitions, The longest path problem is polynomial on cocomparability graphs, On the \(k\)-path partition of graphs., The longest path problem has a polynomial solution on interval graphs, Path covering number and \(L(2,1)\)-labeling number of graphs, Computing and counting longest paths on circular-arc graphs in polynomial time, Finding a minimum path cover of a distance-hereditary graph in polynomial time, Hamiltonian cycle is polynomial on cocomparability graphs, Path partition for graphs with special blocks, An efficient certifying algorithm for the Hamiltonian cycle problem on circular-arc graphs, The Longest Path Problem is Polynomial on Cocomparability Graphs, On the Power of Graph Searching for Cocomparability Graphs, Dominating the complements of bounded tolerance graphs and the complements of trapezoid graphs, Linear-time algorithms for the Hamiltonian problems on distance-hereditary graphs, Hamiltonian powers in threshold and arborescent comparability graphs, Solving the path cover problem on circular-arc graphs by using an approximation algorithm

Cites Work

• Unnamed Item
• Unnamed Item
• Finding Hamiltonian circuits in interval graphs
• A combinatorial bijection between linear extensions of equivalent orders
• Hamiltonian circuits in interval graph generalizations
• Computing the bump number is easy
• Computing the bump number with techniques from two-processor scheduling
• Complement reducible graphs
• Hamiltonian cycle is polynomial on cocomparability graphs
• The Hamiltonian circuit problem for circle graphs is NP-complete
• Domination on Cocomparability Graphs
• The NP-completeness column: an ongoing guide
• Hamilton Paths in Grid Graphs