Finding Hamiltonian paths in cocomparability graphs using the bump number algorithm

DOI10.1007/BF00571188MaRDI QIDQ1198484zbMATH OpenOpenAlexFDO

Authors Peter Damaschke, Jitender Deogun, Dieter Kratsch, George Steiner

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)

Recommendations

• An approximation algorithm for finding long paths in Hamiltonian graphs
• Polynomial Algorithms for Hamiltonian Cycle in Cocomparability Graphs
• An extension of the multi-path algorithm for finding Hamilton cycles
• scientific article; zbMATH DE number 1445365
• An algorithm for finding Hamilton paths and cycles in random graphs
• Algorithms for the optimal Hamiltonian path in Halin graphs
• scientific article; zbMATH DE number 176753
• On Finding Hamiltonian Cycles in Barnette Graphs
• Finding long paths and cycles in sparse Hamiltonian graphs

Cites work

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

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
• The longest path problem is polynomial on cocomparability graphs
• On the power of graph searching for cocomparability graphs
• Weighted domination of cocomparability graphs
• An efficient certifying algorithm for the Hamiltonian cycle problem on circular-arc graphs
• 1-tough cocomparability graphs are hamiltonian
• On \(\lambda\)-backbone coloring of cliques with tree backbones in linear time
• Weighted domination on cocomparability graphs
• Path partition for graphs with special blocks
• Hamiltonian powers in threshold and arborescent comparability graphs
• Polynomial Algorithms for Hamiltonian Cycle in Cocomparability 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
• Computing and counting longest paths on circular-arc graphs in polynomial time
• The decycling number of a line graph
• The Longest Path Problem Is Polynomial on Interval Graphs
• Parameterizing path partitions
• Hamiltonian cycle is polynomial on cocomparability graphs
• Parameterizing path partitions
• 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

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)