2015/06/21 by Barbora Candráková, Candráková, Barbora, Robert Lukoťka +1
Computer Science · Mathematics · #90B10 #90C10 #90C27 #90C59 #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Optimization and Control (math.OC) #cs.DM #math.OC #msc:90B10 #msc:90C10 #msc:90C27 #msc:90C59
paper · pdf · doi:10.48550/arxiv.1506.06369
21 pages
arxiv created 2016/10/12 · arxiv updated 2016/10/13
We prove that every simple bridgeless cubic graph with n >= 8 vertices has a travelling salesman tour of length at most 1.3n - 2, which can be constructed in polynomial time.