Finding and enumerating Hamilton cycles in 4-regular graphs

DOI10.1016/j.tcs.2011.04.038zbMath1226.05143OpenAlexW2008391796MaRDI QIDQ638522

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

regular graphstraveling salesman problemHamilton cycles

Mathematics Subject Classification ID

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

Related Items (5)

Exact algorithms for finding longest cycles in claw-free graphs ⋮ The Asymmetric Travelling Salesman Problem In Sparse Digraphs. ⋮ A new upper bound for the traveling salesman problem in cubic graphs ⋮ An improved exact algorithm for TSP in graphs of maximum degree 4 ⋮ An exact algorithm for TSP in degree-3 graphs via circuit procedure and amortization on connectivity structure

Cites Work

• Unnamed Item
• Unnamed Item
• Enumerating all Hamilton cycles and bounding the number of Hamilton cycles in 3-regular graphs
• A Dynamic Programming Approach to Sequencing Problems
• The Travelling Salesman Problem in Bounded Degree Graphs
• On the number of crossing-free matchings, (cycles, and partitions)
• An Improved Exact Algorithm for Cubic Graph TSP
• On the Number of Hamilton Cycles in Bounded Degree Graphs
• The Traveling Salesman Problem for Cubic Graphs

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