2015/07/25 by Anke van Zuylen, van Zuylen, Anke
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #F.2.2 #FOS: Computer and information sciences #Optimization and Search Problems #cs.DS
paper · pdf · doi:10.48550/arxiv.1507.07121
openalex publication_date 2015/07/25 · arxiv created 2016/06/24 · arxiv updated 2016/06/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We show improved approximation guarantees for the traveling salesman problem on cubic graphs, and cubic bipartite graphs. For cubic bipartite graphs with n nodes, we improve on recent results of Karp and Ravi (2014) by giving a simple "local improvement" algorithm that finds a tour of length at most 5/4 n - 2. For 2-connected cubic graphs, we show that the techniques of Moemke and Svensson (2011) can be combined with the techniques of Correa, Larre and Soto (2012), to obtain a tour of length at most (4/3-1/8754)n.