A new upper bound for the traveling salesman problem in cubic graphs

Maciej Liskiewicz; Martin R. Schuster

doi:10.1016/j.jda.2014.02.001

A new upper bound for the traveling salesman problem in cubic graphs

Maciej Liskiewicz, Martin R. Schuster

Institute of Theoretical Computer Science

5 Citations (Scopus)

Abstract

We provide a new upper bound for traveling salesman problem (TSP) in cubic graphs, i.e. graphs with maximum vertex degree three, and prove that the problem for an n-vertex graph can be solved in O(1.2553ⁿ) time and in linear space. We show that the exact TSP algorithm of Eppstein, with some minor modifications, yields the stated result. The previous best known upper bound O(1.251ⁿ) was claimed by Iwama and Nakashima [Proc. COCOON 2007]. Unfortunately, their analysis contains several mistakes that render the proof for the upper bound invalid.

Original language	English
Journal	Journal of Discrete Algorithms
Volume	27
Pages (from-to)	1-20
Number of pages	20
ISSN	1570-8667
DOIs	https://doi.org/10.1016/j.jda.2014.02.001
Publication status	Published - 07.2014

UN SDGs

This output contributes to the following UN Sustainable Development Goals (SDGs)

Access to Document

10.1016/j.jda.2014.02.001

Cite this

@article{41c962ec4a184fbfbff3f6df6e1120d1,

title = "A new upper bound for the traveling salesman problem in cubic graphs",

abstract = "We provide a new upper bound for traveling salesman problem (TSP) in cubic graphs, i.e. graphs with maximum vertex degree three, and prove that the problem for an n-vertex graph can be solved in O(1.2553n) time and in linear space. We show that the exact TSP algorithm of Eppstein, with some minor modifications, yields the stated result. The previous best known upper bound O(1.251n) was claimed by Iwama and Nakashima [Proc. COCOON 2007]. Unfortunately, their analysis contains several mistakes that render the proof for the upper bound invalid.",

author = "Maciej Liskiewicz and Schuster, {Martin R.}",

year = "2014",

month = jul,

doi = "10.1016/j.jda.2014.02.001",

language = "English",

volume = "27",

pages = "1--20",

journal = "Journal of Discrete Algorithms",

issn = "1570-8667",

}

TY - JOUR

T1 - A new upper bound for the traveling salesman problem in cubic graphs

AU - Liskiewicz, Maciej

AU - Schuster, Martin R.

PY - 2014/7

Y1 - 2014/7

N2 - We provide a new upper bound for traveling salesman problem (TSP) in cubic graphs, i.e. graphs with maximum vertex degree three, and prove that the problem for an n-vertex graph can be solved in O(1.2553n) time and in linear space. We show that the exact TSP algorithm of Eppstein, with some minor modifications, yields the stated result. The previous best known upper bound O(1.251n) was claimed by Iwama and Nakashima [Proc. COCOON 2007]. Unfortunately, their analysis contains several mistakes that render the proof for the upper bound invalid.

AB - We provide a new upper bound for traveling salesman problem (TSP) in cubic graphs, i.e. graphs with maximum vertex degree three, and prove that the problem for an n-vertex graph can be solved in O(1.2553n) time and in linear space. We show that the exact TSP algorithm of Eppstein, with some minor modifications, yields the stated result. The previous best known upper bound O(1.251n) was claimed by Iwama and Nakashima [Proc. COCOON 2007]. Unfortunately, their analysis contains several mistakes that render the proof for the upper bound invalid.

UR - http://www.scopus.com/inward/record.url?scp=84904049822&partnerID=8YFLogxK

U2 - 10.1016/j.jda.2014.02.001

DO - 10.1016/j.jda.2014.02.001

M3 - Journal articles

AN - SCOPUS:84904049822

SN - 1570-8667

VL - 27

SP - 1

EP - 20

JO - Journal of Discrete Algorithms

JF - Journal of Discrete Algorithms

ER -

A new upper bound for the traveling salesman problem in cubic graphs

Abstract

UN SDGs

Access to Document

Other files and links

Cite this