文章基本信息

标题：Graphic TSP in Cubic Graphs
本地全文：下载
作者：Zdenek Dvor{\'a}k ; Daniel Kr{\'a}l ; Bojan Mohar 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2017
卷号：66
页码：27:1-27:13
DOI：10.4230/LIPIcs.STACS.2017.27
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：Graphic TSP; approximation algorithms; cubic graphs