Proceedings of the 2nd International Symposium on Computer, Communication, Control and Automation (ISCCCA 2013)

An Improved Dynamic Programming Algorithm for Bitonic TSP

Authors
Jian Li
Corresponding Author
Jian Li
Available Online February 2013.
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)

Volume Title
Proceedings of the 2nd International Symposium on Computer, Communication, Control and Automation (ISCCCA 2013)
Series
Advances in Intelligent Systems Research
Publication Date
February 2013
ISBN
978-90-78677-63-5
ISSN
1951-6851
DOI
10.2991/isccca.2013.7How to use a DOI?
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/).

Cite this article

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  -