Back to Search
Start Over
An Exact Algorithm for TSP in Degree-3 Graphs Via Circuit Procedure and Amortization on Connectivity Structure.
- Source :
-
Algorithmica . Feb2016, Vol. 74 Issue 2, p713-741. 29p. - Publication Year :
- 2016
-
Abstract
- The paper presents an $$O^*(1.2312^n)$$ -time and polynomial-space algorithm for the traveling salesman problem in an $$n$$ -vertex graph with maximum degree 3. This improves all previous time bounds of polynomial-space algorithms for this problem. Our algorithm is a simple branch-and-search algorithm with only one branch rule designed on a cut-circuit structure of a graph induced by unprocessed edges. To improve a time bound by a simple analysis on measure and conquer, we introduce an amortization scheme over the cut-circuit structure by defining the measure of an instance to be the sum of not only weights of vertices but also weights of connected components of the induced graph. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 01784617
- Volume :
- 74
- Issue :
- 2
- Database :
- Academic Search Index
- Journal :
- Algorithmica
- Publication Type :
- Academic Journal
- Accession number :
- 112694238
- Full Text :
- https://doi.org/10.1007/s00453-015-9970-4