A simple algorithm to find Hamiltonian cycles in proper interval graphs

DOI10.1016/J.IPL.2009.07.010MaRDI QIDQ989586zbMATHOpenAlexFDO

Authors Louis Ibarra

Publication date 20 August 2010

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ipl.2009.07.010

zbMATH Keywords

Hamiltonian cyclegraph algorithmsproper interval graphinterval graphChordal graph

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Eulerian and Hamiltonian graphs (05C45)

Recommendations

• Finding Hamiltonian circuits in interval graphs
• A linear time recognition algorithm for proper interval graphs
• An $O(n^2 \log n)$ Algorithm for the Hamiltonian Cycle Problem on Circular-Arc Graphs
• Linear-time certifying algorithms for the path cover and Hamiltonian cycle problems on interval graphs
• A linear algorithm for finding Hamiltonian cycles in 4-connected maximal planar graphs

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1303554 (Why is no real title available?)
• scientific article; zbMATH DE number 554762 (Why is no real title available?)
• A Fully Dynamic Graph Algorithm for Recognizing Proper Interval Graphs
• A Fully dynamic algorithm for recognizing and representing proper interval graphs
• A linear time recognition algorithm for proper interval graphs
• Algorithmic graph theory and perfect graphs
• An Incremental Linear-Time Algorithm for Recognizing Interval Graphs
• An optimum \(\Theta\) (n log n) algorithm for finding a canonical Hamiltonian path and a canonical Hamiltonian circuit in a set of intervals
• Counting clique trees and computing perfect elimination schemes in parallel
• Fast and Simple Algorithms for Recognizing Chordal Comparability Graphs and Interval Graphs
• Finding Hamiltonian circuits in interval graphs
• Finding Hamiltonian circuits in proper interval graphs
• Linear-Time Representation Algorithms for Proper Circular-Arc Graphs and Proper Interval Graphs
• Proper interval graphs and the guard problem
• Simple linear time recognition of unit interval graphs
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• The NP-completeness column: an ongoing guide
• The clique-separator graph for chordal graphs
• Topics in Intersection Graph Theory

Cited in

(12)

• scientific article; zbMATH DE number 140140 (Why is no real title available?)
• Sitting closer to friends than enemies, revisited
• The Steiner tree in \(K_{1,r}\)-free split graphs -- a dichotomy
• An algorithm for finding all Hamiltonian cycles in a simple graph via hierarchical correlation
• An optimum \(\Theta\) (n log n) algorithm for finding a canonical Hamiltonian path and a canonical Hamiltonian circuit in a set of intervals
• Complexity of Hamiltonian cycle reconfiguration
• Complexity of Steiner tree in split graphs -- dichotomy results
• A data structure useful for finding Hamiltonian cycles
• Finding Hamiltonian circuits in interval graphs
• 2-Trees: Structural insights and the study of Hamiltonian paths
• An $O(n^2 \log n)$ Algorithm for the Hamiltonian Cycle Problem on Circular-Arc Graphs
• Kernelization of graph Hamiltonicity: proper \(H\)-graphs

This page was built for publication: A simple algorithm to find Hamiltonian cycles in proper interval graphs

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