The complexity of finding a second Hamiltonian cycle in cubic graphs

DOI10.1006/JCSS.1998.1611MaRDI QIDQ1307702zbMATH OpenOpenAlexFDO

Authors Adam Krawczyk

Publication date 9 November 1999

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1006/jcss.1998.1611

zbMATH Keywords

cubic graphHamiltonian cycles

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

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

Cites work

• Hamiltonian Cycles and Uniquely Edge Colourable Graphs
• scientific article; zbMATH DE number 3758364 (Why is no real title available?)
• scientific article; zbMATH DE number 3780579 (Why is no real title available?)
• scientific article; zbMATH DE number 125484 (Why is no real title available?)
• scientific article; zbMATH DE number 1263206 (Why is no real title available?)
• On existence theorems
• On the complexity of the parity argument and other inefficient proofs of existence

Cited in

(13)

• Long cycles in Hamiltonian graphs
• A PPA parity theorem about trees in a bipartite graph
• Understanding PPA-completeness
• A parity theorem about trees with specified degrees
• A short note on graphs with long Thomason chains
• A new heuristic for detecting non-Hamiltonicity in cubic graphs
• On the Approximation of Finding A(nother) Hamiltonian Cycle in Cubic Hamiltonian Graphs
• The complexity of Thomason's algorithm for finding a second Hamiltonian cycle
• 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
• Simple algorithm for finding a second Hamilton cycle

This page was built for publication: The complexity of finding a second Hamiltonian cycle in cubic graphs

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