A simple algorithm to find Hamiltonian cycles in proper interval graphs

DOI10.1016/j.ipl.2009.07.010zbMath1197.05085OpenAlexW2059260882MaRDI QIDQ989586

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 algorithmsinterval graphproper interval graphChordal graph

Mathematics Subject Classification ID

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

Related Items (6)

Complexity of Hamiltonian cycle reconfiguration ⋮ The Steiner tree in \(K_{1,r}\)-free split graphs -- a dichotomy ⋮ 2-Trees: Structural insights and the study of Hamiltonian paths ⋮ Complexity of Steiner Tree in Split Graphs - Dichotomy Results ⋮ Kernelization of Graph Hamiltonicity: Proper $H$-Graphs ⋮ Sitting closer to friends than enemies, revisited

Cites Work

• Simple linear time recognition of unit 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
• A linear time recognition algorithm for proper interval graphs
• The clique-separator graph for chordal graphs
• Finding Hamiltonian circuits in proper interval graphs
• Finding Hamiltonian circuits in interval graphs
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Counting clique trees and computing perfect elimination schemes in parallel
• Proper interval graphs and the guard problem
• Algorithmic graph theory and perfect graphs
• A Fully Dynamic Algorithm for Recognizing and Representing Proper Interval Graphs
• A Fully Dynamic Graph Algorithm for Recognizing Proper Interval Graphs
• The NP-completeness column: an ongoing guide
• An Incremental Linear-Time Algorithm for Recognizing Interval Graphs
• Fast and Simple Algorithms for Recognizing Chordal Comparability Graphs and Interval Graphs
• Topics in Intersection Graph Theory
• Linear-Time Representation Algorithms for Proper Circular-Arc Graphs and Proper Interval Graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item

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