APPLICATIONS OF BRANCH-BOUND ALGORITHM TO SOLVE SOME OPTIMAL PROBLEMS RELATED TO THE HAMILTONIAN CYCLE BASED ON THE TSP
DOI:
https://doi.org/10.37569/DalatUniversity.7.2.239(2017)Keywords:
Branch-bound algorithm, Combinatorial optimization problem, Hamiltonian cycle, NP-C (Non-deterministic Polynomial Complete, NP-Hard, Traveling Salesman Problem (TSP).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.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.
Downloads
Published
28-06-2017
Volume and Issues
Section
Natural Sciences and Technology
Copyright & License
Copyright (c) 2017 Đỗ Như An
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
How to Cite
An, Đỗ N. (2017). APPLICATIONS OF BRANCH-BOUND ALGORITHM TO SOLVE SOME OPTIMAL PROBLEMS RELATED TO THE HAMILTONIAN CYCLE BASED ON THE TSP. Dalat University Journal of Science, 7(2), 205-216. https://doi.org/10.37569/DalatUniversity.7.2.239(2017)
