2026-07-23T00:24:12Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:7006 2024-03-06T10:39:11Z ddc:004 open_access

Graphic TSP in Cubic Graphs Dvorák, Zdenek Král, Daniel Mohar, Bojan Graphic TSP approximation algorithms cubic graphs 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Zdenek Dvorák and Daniel Král and Bojan Mohar 2017 Is Part Of LIPIcs, Volume 66, 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2017.27 urn:nbn:de:0030-drops-70068 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2017.27 eng https://creativecommons.org/licenses/by/3.0/legalcode