2016/08/26 by Zdenek Dvorak, Zdenĕk Dvořák, Daniel Král͏̌ +5
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Interconnection Networks and Systems #cs.DM #cs.DS #math.CO
paper · pdf · doi:10.48550/arxiv.1608.07568
openalex publication_date 2016/08/26 · arxiv created 2016/09/05 · arxiv updated 2016/09/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We present a polynomial-time 9/7-approximation algorithm for the graphic TSP for cubic graphs, which improves the previously best approximation factor of 1.3 for 2-connected cubic graphs and drops the requirement of 2-connectivity at the same time. To design our algorithm, we prove that every simple 2-connected cubic n-vertex graph contains a spanning closed walk of length at most 9n/7-1, and that such a walk can be found in polynomial time.