An $O(n^2 \log n)$ Algorithm for the Hamiltonian Cycle Problem on Circular-Arc Graphs
From MaRDI portal
Publication:4027864
DOI10.1137/0221061zbMath0759.68038OpenAlexW2096399406MaRDI QIDQ4027864
No author found.
Publication date: 9 March 1993
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0221061
Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05) Graph theory (including graph drawing) in computer science (68R10)
Related Items (19)
The path-partition problem in block graphs ⋮ Circular convex bipartite graphs: Maximum matching and Hamiltonian circuits ⋮ 1-tough cocomparability graphs are hamiltonian ⋮ \(k\)-path partitions in trees ⋮ Complexity-separating graph classes for vertex, edge and total colouring ⋮ Hamiltonian Cycle in K1,r-Free Split Graphs — A Dichotomy ⋮ 2-Trees: Structural insights and the study of Hamiltonian paths ⋮ Linear-time certifying algorithms for the path cover and Hamiltonian cycle problems on interval graphs ⋮ Hamiltonicity in Split Graphs - A Dichotomy ⋮ Computing and counting longest paths on circular-arc graphs in polynomial time ⋮ Efficient parallel recognition of some circular arc graphs. II ⋮ An efficient certifying algorithm for the Hamiltonian cycle problem on circular-arc graphs ⋮ A linear time recognition algorithm for proper interval graphs ⋮ Jump number maximization for proper interval graphs and series-parallel graphs ⋮ Kernelization of Graph Hamiltonicity: Proper $H$-Graphs ⋮ Linear-time algorithms for the Hamiltonian problems on distance-hereditary graphs ⋮ Revising Johnson's table for the 21st century ⋮ Solving the path cover problem on circular-arc graphs by using an approximation algorithm ⋮ Linear‐Time Algorithms for Scattering Number and Hamilton‐Connectivity of Interval Graphs
This page was built for publication: An $O(n^2 \log n)$ Algorithm for the Hamiltonian Cycle Problem on Circular-Arc Graphs
