Title
An Improved Exact Algorithm for TSP in Graphs of Maximum Degree 4
Abstract
The paper presents a 1.692 -time polynomial-space algorithm for the traveling salesman problem in an -vertex edge-weighted graph with maximum degree 4, which improves the previous results of the 1.890 -time polynomial-space algorithm by Eppstein and the 1.733 -time exponential-space algorithm by Gebauer.
Year
DOI
Venue
2016
10.1007/s00224-015-9612-x
Theory of Computing Systems
Keywords
Field
DocType
Traveling salesman problem,Exact exponential algorithm,Graph algorithm,Measure-and-conquer
Bottleneck traveling salesman problem,Push–relabel maximum flow algorithm,Discrete mathematics,Dinic's algorithm,Combinatorics,Ramer–Douglas–Peucker algorithm,Hopcroft–Karp algorithm,Christofides algorithm,Suurballe's algorithm,2-opt,Mathematics
Journal
Volume
Issue
ISSN
58
2
1432-4350
Citations 
PageRank 
References 
0
0.34
16
Authors
2
Name
Order
Citations
PageRank
Mingyu Xiao116124.70
Hiroshi Nagamochi21513174.40