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

Maciej Liskiewicz, Martin R. Schuster

5 Zitate (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.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.

OriginalspracheEnglisch
ZeitschriftJournal of Discrete Algorithms
Jahrgang27
Seiten (von - bis)1-20
Seitenumfang20
ISSN1570-8667
DOIs
PublikationsstatusVeröffentlicht - 07.2014

Fingerprint

Untersuchen Sie die Forschungsthemen von „A new upper bound for the traveling salesman problem in cubic graphs“. Zusammen bilden sie einen einzigartigen Fingerprint.

Zitieren