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)

zbMATH Keywords

Hamiltonian pathNP-completenessclique partitioningpermutation graphbump numberco-comparability graph

Mathematics Subject Classification ID

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

Cites work

• 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?)
• 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
• HAMILTONian circuits in chordal bipartite graphs
• Hamilton Paths in Grid Graphs
• Hamiltonian cycle is polynomial on cocomparability graphs
• Hamiltonian threshold graphs
• 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 Hamiltonian Circuit Problem is Polynomial for 4-Connected Planar Graphs
• The Hamiltonian circuit problem for circle graphs is NP-complete
• The Hamiltonian problem on distance-hereditary graphs
• The NP-completeness column: An ongoing guide
• The Planar Hamiltonian Circuit Problem is NP-Complete
• The edge Hamiltonian path 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)