Seminár z teoretickej informatiky - Robert Lukoťka (31.3.2017)

v piatok 31.3.2017 o 11:00 hod. v miestnosti M/213

28. 03. 2017 10.53 hod.
Od: Rastislav Královič

Prednášajúci: Róbert Lukoťka

Názov: Travelling salesman problem on cubic and subcubic graphs

Termín: 30.3.2017, 11:00 hod., M/213

Abstrakt:
Dvořák, Kráľ, and Mohar [Z. Dvořák, D. Kráľ, B. Mohar: Graphic TSP in cubic graphs, arXiv:1608.07568] proved that every bridgeless simple $2$-connected cubic graph on $n$ vertices with $n_2$ vertices of degree $2$ contains a spanning closed walk of length at most $9/7 cdot n+2/7 cdot n_2 -1$. We provide a significantly shorter proof of this statement.

Our analysis of $6$-circuits is sufficiently strong, so that limiting aspect for further improvement is the (lack of) analysis of the $7$-circuits. To demostrate this, we provide a basic analysis to slightly improve the constants in the result of Dvořák, Kráľ, and Mohar.

Focusing on circuits of length $6$, we show that a bridgeless cubic graph of girth $6$ has a $2$-factor $F$ that contains $9/13 cdot n$ vertices that are not in $6$-circuits of $F$. The ideas from the proof might provide clues how to further improve the analysis of TSP tours in subcubic graphs.

web: http://kedrigern.dcs.fmph.uniba.sk/STI2
rss: http://kedrigern.dcs.fmph.uniba.sk/STI2/rss.php