Linear-time certifying algorithms for the path cover and Hamiltonian cycle problems on interval graphs

DOI10.1016/J.AML.2010.11.030zbMath1209.05244OpenAlexW1968832374MaRDI QIDQ628259

Ruo-Wei Hung, Maw-Shang Chang

Publication date: 10 March 2011

Published in: Applied Mathematics Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.aml.2010.11.030

zbMATH Keywords

Hamiltonian cycleinterval graphspath covercertifying algorithms

Mathematics Subject Classification ID

Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (11)

Cyclability in graph classes ⋮ The Steiner tree in \(K_{1,r}\)-free split graphs -- a dichotomy ⋮ Disjoint path covers joining prescribed source and sink sets in interval graphs ⋮ On the path partition number of 6‐regular graphs ⋮ 2-Trees: Structural insights and the study of Hamiltonian paths ⋮ Linear-time algorithm for the paired-domination problem in convex bipartite graphs ⋮ An efficient certifying algorithm for the Hamiltonian cycle problem on circular-arc graphs ⋮ Complexity of Steiner Tree in Split Graphs - Dichotomy Results ⋮ Kernelization of Graph Hamiltonicity: Proper $H$-Graphs ⋮ The Steiner cycle and path cover problem on interval graphs ⋮ Linear‐Time Algorithms for Scattering Number and Hamilton‐Connectivity of Interval Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Linear algorithm for optimal path cover problem on 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 simple linear time certifying LBFS-based algorithm for recognizing trivially perfect graphs and their complements
• Interval graphs and maps of DNA
• On mapping processes to processors in distributed systems
• An efficient parallel strategy for the two-fixed-endpoint Hamiltonian path problem on distance-hereditary graphs
• Algorithmic graph theory and perfect graphs
• HAMILTONian circuits in chordal bipartite graphs
• The Hamiltonian problem on distance-hereditary graphs
• Linear-time algorithms for the Hamiltonian problems on distance-hereditary graphs
• Certifying Algorithms for Recognizing Interval Graphs and Permutation Graphs
• An $O(n^2 \log n)$ Algorithm for the Hamiltonian Cycle Problem on Circular-Arc Graphs
• Covering Points of a Digraph with Point-Disjoint Paths and Its Application to Code Optimization
• On Path Cover Problems in Digraphs and Applications to Program Testing
• Deferred-query: An efficient approach for some problems on interval graphs
• Certifying LexBFS Recognition Algorithms for Proper Interval Graphs and Proper Interval Bigraphs

This page was built for publication: Linear-time certifying algorithms for the path cover and Hamiltonian cycle problems on interval graphs