Publication details
Graphic TSP in Cubic Graphs
| Authors | |
|---|---|
| Year of publication | 2017 |
| Type | Article in Periodical |
| Magazine / Source | 34TH SYMPOSIUM ON THEORETICAL ASPECTS OF COMPUTER SCIENCE (STACS 2017) |
| Citation | |
| Doi | http://dx.doi.org/10.4230/LIPIcs.STACS.2017.27 |
| Keywords | Graphic TSP; approximation algorithms; cubic graphs |
| Description | 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. |