The Library
Graphic TSP in cubic graphs
Tools
Tools
Tools
Dvořák, Zdeněk, Králʼ, Daniel and Mohar, Bojan (2017) Graphic TSP in cubic graphs. In: 34th International Symposium on Theoretical Aspects of Computer Science, Hannover, Germany, 8-11 Mar 2017. Published in: Leibniz International Proceedings in Informatics (LIPIcs), 66 ISBN 9783959770286. ISSN 1868-8969.
|
PDF
WRAP-graphic-TSP-cubic-graphs-Kral-2017.pdf - Published Version - Requires a PDF viewer. Available under License Creative Commons Attribution. Download (795Kb) | Preview |
Official URL: http://dx.doi.org/10.4230/LIPIcs.STACS.2017.27
Abstract
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.
| Item Type: | Conference Item (Paper) | ||||||
|---|---|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | ||||||
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science Faculty of Science, Engineering and Medicine > Science > Mathematics |
||||||
| Library of Congress Subject Headings (LCSH): | Computer algorithm., Mathematical optimization., Graph theory. | ||||||
| Journal or Publication Title: | Leibniz International Proceedings in Informatics (LIPIcs) | ||||||
| Publisher: | Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik | ||||||
| ISBN: | 9783959770286 | ||||||
| ISSN: | 1868-8969 | ||||||
| Book Title: | 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017) | ||||||
| Editor: | Vollmer, Heribert and Vallée, Brigitte | ||||||
| Official Date: | 2017 | ||||||
| Dates: |
|
||||||
| Volume: | 66 | ||||||
| Status: | Peer Reviewed | ||||||
| Publication Status: | Published | ||||||
| Date of first compliant deposit: | 25 April 2017 | ||||||
| Date of first compliant Open Access: | 25 April 2017 | ||||||
| Conference Paper Type: | Paper | ||||||
| Title of Event: | 34th International Symposium on Theoretical Aspects of Computer Science | ||||||
| Type of Event: | Other | ||||||
| Location of Event: | Hannover, Germany | ||||||
| Date(s) of Event: | 8-11 Mar 2017 | ||||||
| Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
