Skip to content Skip to navigation
University of Warwick
  • Study
  • |
  • Research
  • |
  • Business
  • |
  • Alumni
  • |
  • News
  • |
  • About

University of Warwick
Publications service & WRAP

Highlight your research

  • WRAP
    • Home
    • Search WRAP
    • Browse by Warwick Author
    • Browse WRAP by Year
    • Browse WRAP by Subject
    • Browse WRAP by Department
    • Browse WRAP by Funder
    • Browse Theses by Department
  • Publications Service
    • Home
    • Search Publications Service
    • Browse by Warwick Author
    • Browse Publications service by Year
    • Browse Publications service by Subject
    • Browse Publications service by Department
    • Browse Publications service by Funder
  • Help & Advice
University of Warwick

The Library

  • Login
  • Admin

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.

[img]
Preview
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

Request Changes to record.

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:
DateEvent
2017Published
11 December 2016Accepted
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:
  • Organisation

Request changes or add full text files to a record

Repository staff actions (login required)

View Item View Item

Downloads

Downloads per month over past year

View more statistics

twitter

Email us: wrap@warwick.ac.uk
Contact Details
About Us