THE COMPLEXITY OF THOMASON’S ALGORITHM FOR FINDING A SECOND HAMILTONIAN CYCLE

DOI10.1017/S0004972718000242zbMath1390.05228OpenAlexW2800672050MaRDI QIDQ4576813

Liang Zhong

Publication date: 11 July 2018

Published in: Bulletin of the Australian Mathematical Society (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1017/s0004972718000242

zbMATH Keywords

Hamiltonian cyclelollipop method

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Eulerian and Hamiltonian graphs (05C45)

Related Items (3)

A parity theorem about trees with specified degrees ⋮ A short note on graphs with long Thomason chains ⋮ A PPA parity theorem about trees in a bipartite graph

Cites Work

• The complexity of finding a second Hamiltonian cycle in cubic graphs
• Hamiltonian Cycles and Uniquely Edge Colourable Graphs
• Reducibility among Combinatorial Problems
• On Hamiltonian Circuits
• Thomason's algorithm for finding a second Hamiltonian circuit through a given edge in a cubic graph is exponential on Krawczyk's graphs

This page was built for publication: THE COMPLEXITY OF THOMASON’S ALGORITHM FOR FINDING A SECOND HAMILTONIAN CYCLE