An Improved Dynamic Programming Algorithm for Bitonic TSP

DOI

10.2991/isccca.2013.7How to use a DOI?

Keywords

dynamic programming, bitonic TSP, optimal sub-structure, space complexity

Abstract

This paper puts forward an improved dynamic programming algorithm for bitonic TSP and it proves to be correct. Divide the whole loop into right-and-left parts through analyzing the key point connecting to the last one directly; then construct a new optimal sub-structure and recursion. The time complexity of the new algorithm is O(n2) and the space complexity is O(n); while both the time and space complexities of the classical algorithm are O(n2). Experiment results showed that the new algorithm not only reduces the space requirement greatly but also increases the computing speed by 2-3 times compared with the classical algorithm.

Copyright

© 2013, the Authors. Published by Atlantis Press.

Open Access

This is an open access article distributed under the CC BY-NC license (http://creativecommons.org/licenses/by-nc/4.0/).

Download article (PDF)

TY  - CONF
AU  - Jian Li
PY  - 2013/02
DA  - 2013/02
TI  - An Improved Dynamic Programming Algorithm for Bitonic TSP
BT  - Proceedings of the 2nd International Symposium on Computer, Communication, Control and Automation (ISCCCA 2013)
PB  - Atlantis Press
SP  - 24
EP  - 27
SN  - 1951-6851
UR  - https://doi.org/10.2991/isccca.2013.7
DO  - 10.2991/isccca.2013.7
ID  - Li2013/02
ER  -