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

Submit your paper
Know more
The week's pick
Responsive image
Improved Shuffled Frog Leaping Algorithm with Self-Adaptive Shuffling for Fuzzy Logic PD+G Controller Optimization in Robotic Manipulators

Duc Hoang Nguyen
Random Articles
Reseach Article

A Note on Computational Approach to Travelling Sales Man Problem

by Shaik Mohiddin Shaw, Dharmaiah Gurram
journal cover thumbnail

International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 115 - Number 8
Year of Publication: 2015
Authors: Shaik Mohiddin Shaw, Dharmaiah Gurram
10.5120/20174-2374

Shaik Mohiddin Shaw, Dharmaiah Gurram . A Note on Computational Approach to Travelling Sales Man Problem. International Journal of Computer Applications. 115, 8 ( April 2015), 28-33. DOI=10.5120/20174-2374

@article{ 10.5120/20174-2374,
author = { Shaik Mohiddin Shaw, Dharmaiah Gurram },
title = { A Note on Computational Approach to Travelling Sales Man Problem },
journal = { International Journal of Computer Applications },
issue_date = { April 2015 },
volume = { 115 },
number = { 8 },
month = { April },
year = { 2015 },
issn = { 0975-8887 },
pages = { 28-33 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume115/number8/20174-2374/ },
doi = { 10.5120/20174-2374 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T22:54:50.838644+05:30
%A Shaik Mohiddin Shaw
%A Dharmaiah Gurram
%T A Note on Computational Approach to Travelling Sales Man Problem
%J International Journal of Computer Applications
%@ 0975-8887
%V 115
%N 8
%P 28-33
%D 2015
%I Foundation of Computer Science (FCS), NY, USA
Abstract

Many real life situations for which there are no optimization algorithms which can solve polynomial time problems in the worst case. So researchers are trying for new approximation algorithms for such kinds of situations. Approximation algorithms give the solution which is close to the optimal solution of a particular situation. Traveling Salesman Problem (TSP) is a typical NP complete problem which lacks polynomial time algorithm. In this paper it is proposed an edge removal algorithm, which will give the nearly optimal solution within a limited time.

References
  1. A. V. Aho, J. E. Hopcroft and J. D. Ullman, "The Design and Analysis of Computer Algorithms", Addison-Wesley, 1974.
  2. E. Horowitz and S. Sahni, "Fundamental of Computer Algorithms" , Computer Science Press, 1982.
  3. E. L. Lawler, J. K. Lenstra, A. RinnooyKan, and D. B. Shmoys. The TravelingSalesman Problem: A Guided Tour of Combinatorial Optimization. Wiley,Chichester, England, 1985.
  4. Goldberg David E, Lingle R Jr. "Alleles, Loci, and the Traveling Salesman Problem. " Proc. Of 1st Int. Conf. on Genetic Algorithms and Their Applications, Lawrence Erlbaum Associates, 1985,154-159
  5. E. L. Lawler, J. K. Lenstra, A. RinnooyKan, and D. B. Shmoys. The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization. Wiley, Chichester, England, 1985.
  6. A. Gibbons and W. Rytter, "Efficient Parallel Algorithms" Cambridge University Press, 1988.
  7. M. Weiss, "Data Structures and Algorithm Analysis", Benjamin-Cummings, 1992.
  8. U. Manber, "Introduction to Algorithms: A Creative approach", Addison-Wesley, 1989.
  9. G. Gonnet and R. Baeza-Yates, "Handbook of Algorithms and Data Structures" , Addison- Wesley, 2 ed. , 1991.
  10. B. Salzberg, "File Structures: An Analytic Approach", Prentice-Hall, 1988.
  11. C. H. Papadimitriou and M. Yannakakis. The traveling salesman problem with distances one and two. Mathematics of Operations Research, 18(1):1–11, 1993.
  12. S. O. Krumke, W. E. de Paepe, D. Poensgen, and L. Stougie. News from the online traveling repairman. In J. Sgall, A. Pultr, and P. Kolman, editors, Proc. 26th Symp. on Mathematical Foundations of Computer Science, volume 2136 of Lecture Notes in Computer Science, pages 487–499. Springer-Verlag, 2001.
  13. Prof. Lenore Cowen, Scribe: Stephanie Tauber, Lecture notes on "The Travelling Salesman Problem (TSP)", Comp260: Advanced Algorithms, Tufts University, Spring 2002.
  14. G. Gutin and A. P. Punnen, editors. The Traveling Salesman Problem and itsVariations. Kluwer, Dordrecht, TheNederlands, 2002.
  15. M. Lipmann. On-Line Routing. PhD thesis, Eindhoven University of Technology, 2003.
  16. K. Chaudhuri, B. Godfrey, S. Rao, and K. Talwar. Paths, trees, and minimum latency tours. In Proceedings of the 44th Annual Symposium on Foundations of Computer Science, Cambridge, Massachusetts, 2003.
  17. C. Chekuri and A. Kumar. Maximum Coverage Problem with Group Budget Constraints and Applications. Proc. Of APPROX-RANDOM, LNCS, 72–83, 2004.
  18. C. Chekuri and M. Pal. A Recursive Greedy Algorithm for Walks in Directed Graphs. Proc. of IEEE FOCS, 245–253, 2005.
  19. C. Chekuri and M. Pal. An O(log n) Approximation for the Asymmetric Traveling Salesman Path Problem. Proc. of APPROX, 95–103, 2005.
  20. K. Chen and S. Har-Peled. The Orienteering Problem in the Plane Revisited. Proc. of ACM SoCG, 247–254, 2006.
  21. V. Nagarajan and R. Ravi. Poly- logarithmic approximation algorithms for Directed Vehicle Routing Problems. Proc. of APPROX, 257–270, 2007.
Index Terms

Computer Science
Information Sciences

Keywords

Edge Removal Algorithm Compression Algorithm Back Tracking.

Powered by PhDFocusTM