Call for Paper - January 2022 Edition
IJCA solicits original research papers for the January 2022 Edition. Last date of manuscript submission is December 20, 2021. Read More

Mutually Nearest Vertex Clusters for Solving TSP

Print
PDF
International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Year of Publication: 2017
Authors:
Govindaraj Pandith T. G., Siddappa M.
10.5120/ijca2017914758

Govindaraj Pandith T G. and Siddappa M.. Mutually Nearest Vertex Clusters for Solving TSP. International Journal of Computer Applications 169(6):1-4, July 2017. BibTeX

@article{10.5120/ijca2017914758,
	author = {Govindaraj Pandith T. G. and Siddappa M.},
	title = {Mutually Nearest Vertex Clusters for Solving TSP},
	journal = {International Journal of Computer Applications},
	issue_date = {July 2017},
	volume = {169},
	number = {6},
	month = {Jul},
	year = {2017},
	issn = {0975-8887},
	pages = {1-4},
	numpages = {4},
	url = {http://www.ijcaonline.org/archives/volume169/number6/27986-2017914758},
	doi = {10.5120/ijca2017914758},
	publisher = {Foundation of Computer Science (FCS), NY, USA},
	address = {New York, USA}
}

Abstract

The Travelling Salesman Problem (TSP) is a classical problem in the field of combinatorial optimization. Main objective of TSP is to find an optimal tour which starts from an arbitrary city (vertex), visits remaining cities exactly once and returns back to the city at which tour commenced. TSP belongs to the class of NP Complete problems, has been studied for many years and is still being studied; a general solution is yet to be reported.

Proximity of cities plays a vital role while traversing a set of cities. Proximity can be traced to a similar measure called distance measure, used in Pattern Recognition (PR). Newer and newer distance measures are proposed in PR for cluster analysis and classification. The sole aim of these measures is to cluster those sets of vertices, which are highly similar or in other words form group of vertices by taking into account distance as a metric of PR from the given instance of complete graph. The objective of this study is to construct a round tour by utilizing the mutually nearest vertices.

References

  1. Satu Elisa Schaeffer 'Graph clustering', ELSEVIER C O M P U T E R S C I E N C E R E V I EW 1 ( 2 0 0 7 ) 2 7 – 6 4 available at www.sciencedirect.com, journal homepage: www.elsevier.com/locate/cosrev
  2. Chetan Chauhan, Ravindra Gupta, Kshitij Pathak “Survey of methods of solving TSP along with its implementation using Dynamic Programming approach” International Journal of Computer Applications, Vol-52,No-4, August 2012
  3. Anshul Singh, Devesh Narayan “A survey paper on Solving Travelling Salesman Problem using Bee colony optimization”, ISSN 2250-2459, Volume 2, Issue 5, May 2012.
  4. Corinne Brucato, “The Travelling Salesman Problem”, University of Pittsburg, 2013.
  5. Anitha Rao, Sandeep Kumar Hegde “Literature Survey On Travelling Salesman Problem Using Genetic Algorithms” International Journal of Advanced Research in Eduation Technology (IJARET) Vol. 2, Issue 1 (Jan. - Mar. 2015) ISSN : 2394-2975 (Online) ISSN : 2394-6814 (Print)
  6. Komal Joshi1, Ram Lal Yadav “A new hybrid approach for solving travelling salesman problem using ordered cross over 1(ox1) and greedy approach” IJRET: International Journal of Research in Engineering and Technology, Volume: 04 Issue: 05 May-2015.
  7. Nearest Neighbour chain algorithm, Wikipedia
  8. Murtagh, Fionn (1983), "A survey of recent advances in hierarchical clustering algorithms" (PDF), The Computer Journal, 26 (4): 354–359, doi:10.1093/comjnl/26.4.354
  9. Murtagh, Fionn (2002), "Clustering in massive data sets", in Abello, James M.; Pardalos, Panos M.; Resende, Mauricio G. C., Handbook of massive data sets, Massive Computing, 4, Springer, pp. 513–516, Bibcode:2002hmds.book.....A, ISBN 978-1-4020-0489-6
  10. Sedgewick, Robert (2004), "Figure 20.7", Algorithms in Java, Part 5: Graph Algorithms (3rd ed.), Addison-Wesley, p. 244, ISBN 0-201-36121-3.

Keywords

TSP, PR, distance measure, cluster analysis and cluster classification.