Activity
Approximating TSP walks in subcubic graphs
Date:2021-12-10

There has been extensive research on approximating TSP walks in subcubic graphs. We show that if G is a 2-connected simple subcubic graph on n vertices with m vertices of degree 2, then G has a TSP walk of length at most 5n/4+m/4-1, establishing a conjecture of Dvořák, Kráľ, and Mohar. This upper bound is best possible.  Our proof implies a quadratic-time algorithm for finding such a TSP walk, thereby giving a 5/4-approximation algorithm for the graphic TSP on simple cubic graphs and improving on the previously best-known approximation ratio of 9/7. This is joint work with Youngho Yoo and Michael Wigal.

Address:No. 6 Science Building, No. 800 Dongchuan Road, Minhang District, Shanghai 200240, China
COPYRIGHT ©2020 Wu Wen-Tsun Center of Mathematical Sciences, Shanghai Jiao Tong University All Rights Reserved 沪交ICP备20200313