Graphic TSP in Cubic Graphs

DVORAK, Z; Daniel KRÁĽ a B MOHAR. Graphic TSP in Cubic Graphs. 34TH SYMPOSIUM ON THEORETICAL ASPECTS OF COMPUTER SCIENCE (STACS 2017). WADEM: SCHLOSS DAGSTUHL, LEIBNIZ CENTER INFORMATICS, 2017, roč. 66, 13 s. ISSN 1868-8969. Dostupné z: https://doi.org/10.4230/LIPIcs.STACS.2017.27.

Základní údaje

Originální název

Graphic TSP in Cubic Graphs

Autoři

DVORAK, Z; Daniel KRÁĽ a B MOHAR

Vydání

34TH SYMPOSIUM ON THEORETICAL ASPECTS OF COMPUTER SCIENCE (STACS 2017), WADEM, SCHLOSS DAGSTUHL, LEIBNIZ CENTER INFORMATICS, 2017, 1868-8969

---

Další údaje

Jazyk

angličtina

Typ výsledku

Článek v odborném periodiku

Utajení

není předmětem státního či obchodního tajemství

Označené pro přenos do RIV

Ne

DOI

https://doi.org/10.4230/LIPIcs.STACS.2017.27

UT WoS

000521077300027

Klíčová slova anglicky

Graphic TSP; approximation algorithms; cubic graphs

---

Anotace

V originále

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.