Linear-time certifying algorithms for the path cover and Hamiltonian cycle problems on interval graphs
From MaRDI portal
Publication:628259
DOI10.1016/j.aml.2010.11.030zbMath1209.05244OpenAlexW1968832374MaRDI QIDQ628259
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
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
- 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
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Linear-time certifying algorithms for the path cover and Hamiltonian cycle problems on interval graphs
