Back to Search
Start Over
An Improved Exact Algorithm for TSP in Graphs of Maximum Degree 4
- Source :
- Theory of Computing Systems. 58:241-272
- Publication Year :
- 2015
- Publisher :
- Springer Science and Business Media LLC, 2015.
-
Abstract
- The paper presents a 1.692nnO(1)-time polynomial-space algorithm for the traveling salesman problem in an n-vertex edge-weighted graph with maximum degree 4, which improves the previous results of the 1.890nnO(1)-time polynomial-space algorithm by Eppstein and the 1.733nnO(1)-time exponential-space algorithm by Gebauer.
- Subjects :
- Discrete mathematics
Push–relabel maximum flow algorithm
Dinic's algorithm
0102 computer and information sciences
02 engineering and technology
2-opt
01 natural sciences
Theoretical Computer Science
Combinatorics
Computational Theory and Mathematics
010201 computation theory & mathematics
Ramer–Douglas–Peucker algorithm
Christofides algorithm
0202 electrical engineering, electronic engineering, information engineering
020201 artificial intelligence & image processing
Suurballe's algorithm
Bottleneck traveling salesman problem
Hopcroft–Karp algorithm
Mathematics
Subjects
Details
- ISSN :
- 14330490 and 14324350
- Volume :
- 58
- Database :
- OpenAIRE
- Journal :
- Theory of Computing Systems
- Accession number :
- edsair.doi...........055b45d6770810160e389f58b1913f73