Finding Hamiltonian paths in cocomparability graphs using the bump number algorithm

DOI10.1007/BF00571188zbMATH Open0760.05063OpenAlexW2089894925MaRDI QIDQ1198484FDOQ1198484

George Steiner, Jitender 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

partial ordercyclepathpermutation graphscocomparability graphbump number algorithmHamiltonian Path problem

Mathematics Subject Classification ID

Eulerian and Hamiltonian graphs (05C45)

Cites Work

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

Cited In (28)

• Path covering number and \(L(2,1)\)-labeling number of graphs
• Linear-time algorithms for the Hamiltonian problems on distance-hereditary graphs
• Solving the path cover problem on circular-arc graphs by using an approximation algorithm
• On the power of graph searching for cocomparability graphs
• Weighted domination of cocomparability graphs
• On \(\lambda\)-backbone coloring of cliques with tree backbones in linear time
• An efficient certifying algorithm for the Hamiltonian cycle problem on circular-arc graphs
• 1-tough cocomparability graphs are hamiltonian
• Weighted domination on cocomparability graphs
• The Longest Path Problem is Polynomial on Cocomparability Graphs
• Path partition for graphs with special blocks
• Polynomial Algorithms for Hamiltonian Cycle in Cocomparability Graphs
• Hamiltonian powers in threshold and arborescent comparability graphs
• HAMILTONian circuits in chordal bipartite graphs
• Finding a minimum path cover of a distance-hereditary graph in polynomial time
• Dominating the complements of bounded tolerance graphs and the complements of trapezoid graphs
• The longest path problem is polynomial on cocomparability graphs
• The longest path problem has a polynomial solution on interval graphs
• The decycling number of a line graph
• Computing and counting longest paths on circular-arc graphs in polynomial time
• The Longest Path Problem Is Polynomial on Interval Graphs
• Parameterizing path partitions
• Parameterizing path partitions
• Hamiltonian cycle is polynomial on cocomparability graphs
• Toughness, hamiltonicity and split graphs
• A Heuristic for Finding Compatible Differential Paths with Application to HAS-160
• On the \(k\)-path partition of graphs.
• Cyclability in graph classes

Recommendations

• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• An algorithm for finding Hamilton paths and cycles in random graphs 👍 👎
• Polynomial Algorithms for Hamiltonian Cycle in Cocomparability Graphs 👍 👎
• An approximation algorithm for finding long paths in Hamiltonian graphs 👍 👎
• Finding long paths and cycles in sparse Hamiltonian graphs 👍 👎
• An extension of the multi-path algorithm for finding Hamilton cycles 👍 👎
• On Finding Hamiltonian Cycles in Barnette Graphs 👍 👎

This page was built for publication: Finding Hamiltonian paths in cocomparability graphs using the bump number algorithm

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1198484)