
The Library
Graphic TSP in cubic graphs
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