Finding Hamiltonian paths in cocomparability graphs using the bump number algorithm
From MaRDI portal
The cocomparability graph of a partial order is the graph whose edges are the incomparable pairs in the partial order. It is shown that the Hamiltonian Path problem can be solved in polynomial time for cocomparability graphs, and thus for the subclass of permutation graphs. The proof uses results on the bump numbers of partially ordered sets, and relationships between Hamiltonian paths in the cocomparability graphs and the bump numbers. The existence of polynomial time algorithms for path (cycle) completion problems in cocomparability graphs is proved.
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
- 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
- scientific article; zbMATH DE number 3900817 (Why is no real title available?)
- scientific article; zbMATH DE number 3893249 (Why is no real title available?)
- The Hamiltonian circuit problem for circle graphs is NP-complete
- The NP-completeness column: an ongoing guide
Cited in
(31)- Hamiltonian cycle is polynomial on cocomparability graphs
- Hamiltonian powers in threshold and arborescent comparability graphs
- 1-tough cocomparability graphs are hamiltonian
- Weighted domination of cocomparability graphs
- On the \(k\)-path partition of graphs.
- Path partition for graphs with special blocks
- Dominating the complements of bounded tolerance graphs and the complements of trapezoid graphs
- Toughness, hamiltonicity and split graphs
- HAMILTONian circuits in chordal bipartite graphs
- The longest path problem is polynomial on cocomparability 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
- 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
- A Heuristic for Finding Compatible Differential Paths with Application to HAS-160
- The longest path problem is polynomial on cocomparability graphs
- The Longest Path Problem Is Polynomial on Interval Graphs
- Polynomial Algorithms for Hamiltonian Cycle in Cocomparability Graphs
- Parameterizing path partitions
- The longest path problem has a polynomial solution on interval graphs
- Weighted domination on cocomparability graphs
- On \(\lambda\)-backbone coloring of cliques with tree backbones in linear time
- The decycling number of a line graph
- Parameterizing path partitions
- On the structure of Hamiltonian graphs with small independence number
- Hamiltonian path in permutation graphs
- On the structure of Hamiltonian graphs with small independence number
- An efficient certifying algorithm for the Hamiltonian cycle problem on circular-arc 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)
