CFP last date

by
Evans Baidoo

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

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.

- http://en.wikipedia.org/wiki/Travelling salesman problem.
- 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.
- 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
- 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
- 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.
- 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
- Li, W.2011. A Parallel Multi-Start Search Algorithm for Dynamic Traveling Salesman Problem. 10th International Conference on Experimental Algorithm, pp 65-75, 2011.
- 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.
- http://www.geeksforgeeks.org/greedy-algorithms-set-5-prims-minimum-spanning-tree-mst-2/
- 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.
- https://people.sc.fsu.edu/~jburkardt/datasets/tsp/tsp.html
- 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.
- 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.
- Pierce, A. R. 1974. Bibliography on algorithms for shortest path, shortest spanning tree and related circuit routing problems (1956}1974). Networks1975;5:129}49.
- Fredman, M. L., and Tarjan, R. E. 1987. Fibonacci heaps and their uses in improved network optimizationalgorithms. J. ACM 34, 596–615.
- 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.
- 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
- http://www.csl.mtu.edu/cs4321/www/Lectures/Lecture%2028%20-%20Approximation%20Algorithm.htm
- Lawler, E. L, Lenstra, J. K., Rinnooy Kan, A.H.G and.Shmoys, D.B 1985. The Traveling Salesman Problem. John Wiley & Sons.
- 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

Computer Science

Information Sciences