Exécution de notre outil de synthèse sur un nouvel article

Vérifiez l’article ci-dessous, puis lancez sa synthèse.


Graphic TSP in 2-connected cubic graphs

Zdenek Dvorak, Daniel Kral, Bojan Mohar

Résumé : 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. This yields a polynomial-time 9/7-approximation algorithm for the graphic TSP for 2-connected cubic graphs, which improves the previously known approximation factor of 1.3 for 2-connected cubic graphs. On the negative side, we show that there exist simple 2-connected cubic n-vertex graphs with no spanning closed walk of length less than 5n/4-1.

Soumis à arXiv le 26 Aoû. 2016