APPLICATIONS OF BRANCH-BOUND ALGORITHM TO SOLVE SOME OPTIMAL PROBLEMS RELATED TO THE HAMILTONIAN CYCLE BASED ON THE TSP

Đỗ Như An

Abstract


The Traveling Salesman Problem (TSP) is the most prominent of the combinatorial optimization problems that belongs to NP-Hard. The best algorithm for solving TSP is the branch-bound algorithm with exponential-time complexity. This paper presents how to use the branch-bound algorithm to solve some of the combinatorial optimization problems related to the Hamiltonian cycle based on the TSP.

Keywords


Branch-bound algorithm; Combinatorial optimization problem; Hamiltonian cycle; NP-C (Non-deterministic Polynomial Complete; NP-Hard; Traveling Salesman Problem (TSP).

References


Dantzig, G., Fulkerson, D., & Johnson, S. (1954). Solution of large-scale traveling salesman problem. Journal of the Operations Research Society of America, 10(3), 393-410.

Ding, Z. D. (2001). Theory of computational complexity. New Jersey, USA: Wiley-Interscience.

Korter, B., & Vygen, J. (2002). Combinatorial optimization: Theory and algorithms. Berlin,Gemany: Springer.

Lawler, E. L., & Lenstra, J. K. (1985). The traveling salesman problem. New Jersey, USA: John Wiley & Sons.




DOI: http://dx.doi.org/10.37569/DalatUniversity.7.2.239(2017)

Refbacks

  • There are currently no refbacks.


Copyright (c) 2017 Đỗ Như An

Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
Editorial Office of DLU Journal of Science
Room.15, A25 Building, 01 Phu Dong Thien Vuong Street, Dalat, Lamdong
Email: tapchikhoahoc@dlu.edu.vn - Phone: (+84) 263 3 555 131

Creative Commons License
Based on Open Journal Systems
Developed by Information Technology Department