CFP last date
02 December 2024
Call for Paper
January Edition
CAE solicits high quality original research papers for the upcoming January edition of the journal. The last date of research paper submission is 02 December 2024

Submit your paper
Know more
The week's pick
Responsive image
Property (Land) Registration Management Using Blockchain in Nigeria

A. Festus Osuolale Ojebiyi David-Daniel Seriki Oluwasogo
Random Articles
Reseach Article

A Preliminary Study on Minimum Spanning Tree Algorithm Approach for Travelling Salesman Problem

by Evans Baidoo
journal cover thumbnail

Communications on Applied Electronics
Foundation of Computer Science (FCS), NY, USA
Volume 5 - Number 10
Year of Publication: 2016
Authors: Evans Baidoo
10.5120/cae2016652386

Evans Baidoo . A Preliminary Study on Minimum Spanning Tree Algorithm Approach for Travelling Salesman Problem. Communications on Applied Electronics. 5, 10 ( Sep 2016), 29-36. DOI=10.5120/cae2016652386

@article{ 10.5120/cae2016652386,
author = { Evans Baidoo },
title = { A Preliminary Study on Minimum Spanning Tree Algorithm Approach for Travelling Salesman Problem },
journal = { Communications on Applied Electronics },
issue_date = { Sep 2016 },
volume = { 5 },
number = { 10 },
month = { Sep },
year = { 2016 },
issn = { 2394-4714 },
pages = { 29-36 },
numpages = {9},
url = { https://www.caeaccess.org/archives/volume5/number10/659-2016652386/ },
doi = { 10.5120/cae2016652386 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2023-09-04T19:55:50.103516+05:30
%A Evans Baidoo
%T A Preliminary Study on Minimum Spanning Tree Algorithm Approach for Travelling Salesman Problem
%J Communications on Applied Electronics
%@ 2394-4714
%V 5
%N 10
%P 29-36
%D 2016
%I Foundation of Computer Science (FCS), NY, USA
Abstract

Much attention has be drawn by the Travelling salesman problem lately as it is one of the problem in mathematics and computer science which although is easy to understand but very difficult to solve. In this paper, a preliminary study is undertaken to construct a minimum spanning tree algorithm to approximately solve the TSP. An implementation of the travelling salesman problem using a modified pure minimum spanning tree algorithm is also presented. The propose algorithm provides an evaluation of the cost of a round trip and it executes in practical time. The algorithm verifies from a constructed tour and presents a shortcut path to all destinations. The proposed approach performance is benchmark with a case study.

References
  1. http://en.wikipedia.org/wiki/Travelling salesman problem.
  2. Whitely, D., Starkweather, T. and D’Ann, F. 1989. Scheduling problems and traveling salesman: The genetic edge recombination operator, in Proc.3rd Int. Conf. Genetic Algorithms, 1989, pp.133–140.
  3. Clarke, G. and Wright, J.W. 1964. Scheduling of vehicles from a central depot to a number of delivery points, Oper. Res., vol. 12, pp. 568–581, 1964.G. http://dx.doi.org/10.1287/opre.12.4.568
  4. Korostensky, C. and Gonnet, G. H. 2000. Using traveling salesman problem algorithms for evolutionary tree construction, Bioinformatics, vol. 16, no. 7, pp. 619–627, 2000. http://dx.doi.org/10.1093/bioinformatics/16.7.61
  5. Alizadeh, F., Karp, R. M., Newberg, L. A. and Weisser D. K., 1993. Physical mapping of chromosomes: A combinatorial problem in molecular biology, in Proc. 4th ACM-SIAM Symp. Discrete Algorithms (SODA), 1993, pp. 52–76.
  6. Kirkpatrick, S., Gelatt Jr, C. D. and Vecchi, M. P. 1983. Optimization by simulated annealing, Science, vol. 220, pp. 498–516, 1983. http://dx.doi.org/10.1126/science.220.4598.671
  7. Li, W.2011. A Parallel Multi-Start Search Algorithm for Dynamic Traveling Salesman Problem. 10th International Conference on Experimental Algorithm, pp 65-75, 2011.
  8. R. Matai, S. Singh, M. L. Mittal,“Traveling Salesman Problem: an Overview of Applications, Formulations, and Solution Approaches,”Traveling Salesman Problem, Theory and Applications. InTech, 2010.
  9. http://www.geeksforgeeks.org/greedy-algorithms-set-5-prims-minimum-spanning-tree-mst-2/
  10. Hendtlass, T. 2010. TSP Optimisation Using Multi Tours Ants, 17th International Conference on Industrial and Engineering Applications of Artificial Intelligence and Expert Systems, pp. 523-532, 2010.
  11. https://people.sc.fsu.edu/~jburkardt/datasets/tsp/tsp.html
  12. Graham, R. L., and Hell, P. 1985. On the history of the minimum spanning tree problem. Annals of the History of Computing 1985;7:43}57.
  13. Maffioli, F. 1981. Complexity of optimum undirected tree problems: a survey of recent results. In: Ausiello G, Lucertini M, editors. Analysis and design of algorithms in combinatorial optimization. International Center for Mechanical Sciences. CISM Courses and Lectures, 266. New York: Springer, 1981. p. 107}28.
  14. Pierce, A. R. 1974. Bibliography on algorithms for shortest path, shortest spanning tree and related circuit routing problems (1956}1974). Networks1975;5:129}49.
  15. Fredman, M. L., and Tarjan, R. E. 1987. Fibonacci heaps and their uses in improved network optimizationalgorithms. J. ACM 34, 596–615.
  16. Gabow, H. N., Galil, Z., Spencer, T., and Tarjan, R. E. 1986. Efficient algorithms for finding minimum spanning trees in undirected and directed graphs. Combinatorica 6, 109–122.
  17. Cuneyt F. B. and Khalil S. H. 2001. Minimum-weight spanning tree algorithms. A survey and empirical study, Computer & Operations Research 28(2001) 767-785
  18. http://www.csl.mtu.edu/cs4321/www/Lectures/Lecture%2028%20-%20Approximation%20Algorithm.htm
  19. Lawler, E. L, Lenstra, J. K., Rinnooy Kan, A.H.G and.Shmoys, D.B 1985. The Traveling Salesman Problem. John Wiley & Sons.
  20. Sharad, N. et al. 2013. Solving Travelling Salesman Problem using Firefly Algorithm. International Journal for Research in Science & Advanced Technologies Issue-2, Volume-2, 053-057
Index Terms

Computer Science
Information Sciences

Keywords

Minimum Spanning Tree Travelling Salesman Problem

Powered by PhDFocusTM