An efficient certifying algorithm for the Hamiltonian cycle problem on circular-arc graphs
type: Item
instance of: scholarly article
title: An efficient certifying algorithm for the Hamiltonian cycle problem on circular-arc graphs
zbMATH Open document ID: 1235.68083
author: Ruo-Wei Hung
author: Maw-Shang Chang
published in: Theoretical Computer Science
publication date: 2011-10-10T00:00:00Z
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 05C45
zbMATH DE Number: 5955893
zbMATH Keywords: certifying algorithm
zbMATH Keywords: Hamiltonian cycle
zbMATH Keywords: path cover
zbMATH Keywords: interval graphs
zbMATH Keywords: circular-arc graphs
MaRDI profile type: Publication
full work available at URL: j.tcs.2011.06.009
OpenAlex ID: W2008676475
cites work: Linear algorithm for optimal path cover problem on interval graphs
cites work: Q4875843
cites work: Q4094891
cites work: Hamiltonian circuits in interval graph generalizations
cites work: Minimum node disjoint path covering for circular-arc graphs
cites work: Deferred-query—An efficient approach for problems on interval and circular-arc graphs
cites work: Deferred-query: An efficient approach for some problems on interval graphs
cites work: Solving the all-pair shortest path query problem on interval and circular-arc graphs
cites work: A simple linear time certifying LBFS-based algorithm for recognizing trivially perfect graphs and their complements
cites work: The Hamiltonian circuit problem for circle graphs is NP-complete
cites work: Finding Hamiltonian paths in cocomparability graphs using the bump number algorithm
cites work: Paths in interval graphs and circular arc graphs
cites work: Polynomial Algorithms for Hamiltonian Cycle in Cocomparability Graphs
cites work: Q4256006
cites work: Q3140413
cites work: Q4198056
cites work: Algorithmic graph theory and perfect graphs
cites work: Q5503435
cites work: Certifying LexBFS Recognition Algorithms for Proper Interval Graphs and Proper Interval Bigraphs
cites work: Linear-time certifying algorithms for near-graphical sequences
cites work: The Hamiltonian problem on distance-hereditary graphs
cites work: Linear time algorithms on circular-arc graphs
cites work: $O(M\cdot N)$ Algorithms for the Recognition and Isomorphism Problems on Circular-Arc Graphs
cites work: Hamilton cycles in split graphs with large minimum degree
cites work: Linear-time algorithms for the Hamiltonian problems on distance-hereditary graphs
cites work: Solving the path cover problem on circular-arc graphs by using an approximation algorithm
cites work: Linear-time certifying algorithms for the path cover and Hamiltonian cycle problems on interval graphs
cites work: Hamilton Paths in Grid Graphs
cites work: The NP-completeness column: an ongoing guide
cites work: Certifying algorithms for recognizing proper circular-arc graphs and unit circular-arc graphs
cites work: Q4471290
cites work: Certifying Algorithms for Recognizing Interval Graphs and Permutation Graphs
cites work: Q3998976
cites work: An optimum \(\Theta\) (n log n) algorithm for finding a canonical Hamiltonian path and a canonical Hamiltonian circuit in a set of intervals
cites work: An Optimal Algorithm for Finding a Maximum Independent Set of a Circular-Arc Graph
cites work: Linear-time recognition of circular-arc graphs
cites work: Certifying algorithms
cites work: An O(nm)-Time Certifying Algorithm for Recognizing HHD-Free Graphs
cites work: Q3992847
cites work: Q4862336
cites work: An $O(n^2 \log n)$ Algorithm for the Hamiltonian Cycle Problem on Circular-Arc Graphs
cites work: Q3685231
cites work: An Efficient Test for Circular-Arc Graphs
cites work: Interval graphs and maps of DNA
DOI: 10.1016/J.TCS.2011.06.009
description: scientific article; zbMATH DE number 5955893