Finding and enumerating Hamilton cycles in 4-regular graphs

DOI10.1016/J.TCS.2011.04.038MaRDI QIDQ638522zbMATH OpenOpenAlexFDO

Authors Heidi Gebauer

Publication date 12 September 2011

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2011.04.038

zbMATH Keywords

traveling salesman problemHamilton cyclesregular graphs

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38)

Recommendations

• \(4\)-regular \(4\)-connected Hamiltonian graphs with a bounded number of Hamiltonian cycles
• Counting Hamiltonian cycles on quartic 4-vertex-connected planar graphs
• Hamiltonian paths and cycles in some 4-uniform hypergraphs
• Hamiltonian cycles in regular graphs
• scientific article; zbMATH DE number 31019
• On the minimum number of Hamiltonian cycles in regular graphs
• Hamiltonicity of 4-connected graphs
• Enumerating all Hamilton cycles and bounding the number of Hamilton cycles in 3-regular graphs
• A linear algorithm for finding Hamiltonian cycles in 4-connected maximal planar graphs
• Finding Hamiltonian cycles in certain planar graphs

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1953201 (Why is no real title available?)
• A Dynamic Programming Approach to Sequencing Problems
• An Improved Exact Algorithm for Cubic Graph TSP
• Enumerating all Hamilton cycles and bounding the number of Hamilton cycles in 3-regular graphs
• On the number of Hamilton cycles in bounded degree graphs
• On the number of crossing-free matchings, (cycles, and partitions)
• The Traveling Salesman Problem for Cubic Graphs
• The Travelling Salesman Problem in Bounded Degree Graphs

Cited in

(16)

• Exact algorithms for finding longest cycles in claw-free graphs
• scientific article; zbMATH DE number 409961 (Why is no real title available?)
• The Asymmetric Travelling Salesman Problem In Sparse Digraphs.
• On the minimum number of Hamiltonian cycles in regular graphs
• Enumerating all Hamilton cycles and bounding the number of Hamilton cycles in 3-regular graphs
• Hamiltonian paths and cycles in some 4-uniform hypergraphs
• On the number of Hamilton cycles in bounded degree graphs
• Solution to an open problem on 4-ordered Hamiltonian graphs
• Estimation of the number of Hamiltonian cycles in regular graphs of special type
• Parameterized algorithms in smooth 4-regular Hamiltonian graphs
• A new upper bound for the traveling salesman problem in cubic graphs
• An improved exact algorithm for TSP in graphs of maximum degree 4
• \(4\)-regular \(4\)-connected Hamiltonian graphs with a bounded number of Hamiltonian cycles
• Counting Hamiltonian cycles on quartic 4-vertex-connected planar graphs
• Generating 4-regular Hamiltonian plane graphs
• Finding a second Hamiltonian decomposition of a 4-regular multigraph by integer linear programming

This page was built for publication: Finding and enumerating Hamilton cycles in 4-regular graphs

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