Informace o publikaci
Graphic TSP in Cubic Graphs
| Autoři | |
|---|---|
| Rok publikování | 2017 |
| Druh | Článek v odborném periodiku |
| Časopis / Zdroj | 34TH SYMPOSIUM ON THEORETICAL ASPECTS OF COMPUTER SCIENCE (STACS 2017) |
| Citace | |
| Doi | http://dx.doi.org/10.4230/LIPIcs.STACS.2017.27 |
| Klíčová slova | Graphic TSP; approximation algorithms; cubic graphs |
| Popis | 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. |