An efficient certifying algorithm for the Hamiltonian cycle problem on circular-arc graphs
From MaRDI portal
Publication:719277
DOI10.1016/j.tcs.2011.06.009zbMath1235.68083OpenAlexW2008676475MaRDI QIDQ719277
Publication date: 10 October 2011
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2011.06.009
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Eulerian and Hamiltonian graphs (05C45)
Related Items (3)
On a Verification Framework for Certifying Distributed Algorithms: Distributed Checking and Consistency ⋮ Unnamed Item ⋮ Hamiltonian Cycle in K1,r-Free Split Graphs — A Dichotomy
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Certifying algorithms
- Linear-time certifying algorithms for the path cover and Hamiltonian cycle problems on interval graphs
- 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
- Certifying algorithms for recognizing proper circular-arc graphs and unit circular-arc graphs
- Linear-time certifying algorithms for near-graphical sequences
- Interval graphs and maps of DNA
- Hamiltonian circuits in interval graph generalizations
- Linear time algorithms on circular-arc graphs
- Finding Hamiltonian paths in cocomparability graphs using the bump number algorithm
- Paths in interval graphs and circular arc graphs
- Minimum node disjoint path covering for circular-arc graphs
- Linear-time recognition of circular-arc graphs
- The Hamiltonian circuit problem for circle graphs is NP-complete
- Algorithmic graph theory and perfect graphs
- The Hamiltonian problem on distance-hereditary graphs
- Linear-time algorithms for the Hamiltonian problems on distance-hereditary graphs
- Solving the path cover problem on circular-arc graphs by using an approximation algorithm
- Certifying Algorithms for Recognizing Interval Graphs and Permutation Graphs
- An O(nm)-Time Certifying Algorithm for Recognizing HHD-Free Graphs
- The NP-completeness column: an ongoing guide
- An Optimal Algorithm for Finding a Maximum Independent Set of a Circular-Arc Graph
- An Efficient Test for Circular-Arc Graphs
- An $O(n^2 \log n)$ Algorithm for the Hamiltonian Cycle Problem on Circular-Arc Graphs
- Deferred-query: An efficient approach for some problems on interval graphs
- Polynomial Algorithms for Hamiltonian Cycle in Cocomparability Graphs
- Solving the all-pair shortest path query problem on interval and circular-arc graphs
- Hamilton Paths in Grid Graphs
- Hamilton cycles in split graphs with large minimum degree
- $O(M\cdot N)$ Algorithms for the Recognition and Isomorphism Problems on Circular-Arc Graphs
- Deferred-query—An efficient approach for problems on interval and circular-arc graphs
- Certifying LexBFS Recognition Algorithms for Proper Interval Graphs and Proper Interval Bigraphs
This page was built for publication: An efficient certifying algorithm for the Hamiltonian cycle problem on circular-arc graphs
