The complexity of Thomason's algorithm for finding a second Hamiltonian cycle

DOI10.1017/S0004972718000242MaRDI QIDQ4576813zbMATH OpenOpenAlexFDO

Authors 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) Eulerian and Hamiltonian graphs (05C45) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• The complexity of finding a second Hamiltonian cycle in cubic graphs
• Thomason's algorithm for finding a second Hamiltonian circuit through a given edge in a cubic graph is exponential on Krawczyk's graphs
• A lower bound on the number of hamiltonian cycles
• Simple algorithm for finding a second Hamilton cycle
• On the Approximation of Finding A(nother) Hamiltonian Cycle in Cubic Hamiltonian Graphs

Cites work

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

Cited in

(11)

• The complexity of finding a second Hamiltonian cycle in cubic graphs
• A PPA parity theorem about trees in a bipartite graph
• A parity theorem about trees with specified degrees
• A short note on graphs with long Thomason chains
• On the Approximation of Finding A(nother) Hamiltonian Cycle in Cubic Hamiltonian Graphs
• scientific article; zbMATH DE number 7559398 (Why is no real title available?)
• Thomason's algorithm for finding a second Hamiltonian circuit through a given edge in a cubic graph is exponential on Krawczyk's graphs
• The complexity of iterated reversible computation
• Another Hamiltonian cycle in bipartite Pfaffian graphs
• Chords in longest cycles in 3-connected graphs
• Simple algorithm for finding a second Hamilton cycle

This page was built for publication: The complexity of Thomason's algorithm for finding a second Hamiltonian cycle

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4576813)