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

DOI10.1016/J.AML.2010.11.030zbMATH Open1209.05244OpenAlexW1968832374MaRDI QIDQ628259FDOQ628259

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

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

Cites Work

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

Cited In (15)

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

   Recommendations

• An efficient certifying algorithm for the Hamiltonian cycle problem on circular-arc graphs 👍 👎
• An $O(n^2 \log n)$ Algorithm for the Hamiltonian Cycle Problem on Circular-Arc Graphs 👍 👎
• Certifying Algorithms for Recognizing Interval Graphs and Permutation Graphs 👍 👎
• Title not available (Why is that?) 👍 👎
• Paths in interval graphs and circular arc graphs 👍 👎

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

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