Hamiltonian path in permutation graphs

DOI10.1016/J.TCS.2025.115301MaRDI QIDQ6971747zbMATH OpenFDO

Authors Krishna Daripa, Alak Kumar Datta

Publication date 13 June 2025

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.TCS.2025.115301

zbMATH Keywords

bump numberclique partitioningco-comparability graphHamiltonian pathNP-completenesspermutation graph

Mathematics Subject Classification ID

Eulerian and Hamiltonian graphs (05C45) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Review text

The Hamiltonian path problem is NP-complete for general graphs. The notion of a follow-up vertex in a permutation graph is introduced in this research, with respect to its Hasse diagram. A necessary and sufficient condition is justified for the existence of a Hamiltonian path in a permutation graph in terms of the existence of a follow-up vertex. Specifically, it is proved that a permutation graph has a Hamiltonian path if and only if it has a follow-up vertex in its lowest layer in the Hasse diagram. A number of improved algorithms are developed using the findings on follow-up vertices to find solutions to the Hamiltonian path problem in permutation graphs that run in \(n(\log (\log n)\) time.

Cites work

• A linear time recognition algorithm for proper interval graphs
• A simple algorithm to find Hamiltonian cycles in proper interval graphs
• An $O(n^2 \log n)$ Algorithm for the Hamiltonian Cycle Problem on Circular-Arc Graphs
• An optimum \(\Theta\) (n log n) algorithm for finding a canonical Hamiltonian path and a canonical Hamiltonian circuit in a set of intervals
• Complement reducible graphs
• Computing the bump number is easy
• Efficient algorithms for finding depth-first and breadth-first search trees in permutation graphs
• Fast algorithms for finding Hamiltonian paths and cycles in in-tournament digraphs
• Finding Hamiltonian circuits in interval graphs
• Finding Hamiltonian paths in cocomparability graphs using the bump number algorithm
• Hamilton Paths in Grid Graphs
• HAMILTONian circuits in chordal bipartite graphs
• Hamiltonian cycle is polynomial on cocomparability graphs
• Hamiltonian threshold graphs
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 3290993 (Why is no real title available?)
• Linear-time algorithms for the Hamiltonian problems on distance-hereditary graphs
• Mathematical tools for data mining. Set theory, partial orders, combinatorics
• Notes on Hamiltonian threshold and chain graphs
• On Comparability and Permutation Graphs
• Partially ordered sets.
• Permutation Graphs and Transitive Graphs
• Polynomial Algorithms for Hamiltonian Cycle in Cocomparability Graphs
• Preserving order in a forest in less than logarithmic time and linear space
• The edge Hamiltonian path problem is NP-complete
• The Hamiltonian circuit problem for circle graphs is NP-complete
• The Hamiltonian Circuit Problem is Polynomial for 4-Connected Planar Graphs
• The Hamiltonian problem on distance-hereditary graphs
• The NP-completeness column: An ongoing guide
• The Planar Hamiltonian Circuit Problem is NP-Complete
• Transitive Orientation of Graphs and Identification of Permutation Graphs

This page was built for publication: Hamiltonian path in permutation graphs

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