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
Authors: 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
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
- scientific article; zbMATH DE number 2079335
- Paths in interval graphs and circular arc graphs
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
- Linear-time certifying recognition algorithms and forbidden induced subgraphs
- 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 (17)
- Linear-Time Algorithms for Scattering Number and Hamilton-Connectivity of Interval Graphs
- Kernelization of Graph Hamiltonicity: Proper $H$-Graphs
- A simple algorithm to find Hamiltonian cycles in proper interval 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
- Certifying Algorithms for Recognizing Interval Graphs and Permutation 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
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)
