Study on Euclidian TSP and asymmetric TSP with reference to graph theory

  Monika Yadav,  Dr. Ashutosh

Like the general TSP, the Euclidean TSP (and therefore the general metric TSP) is NP-complete. However, in some respects it seems to be easier than the general metric TSP. For example, the minimum spanning tree of the graph associated with an instance of the Euclidean TSP is a Euclidean minimum spanning tree, and so can be computed in expected O(n log n) time for n points (considerably less than the number of edges). This enables the simple 2-approximation algorithm for TSP with triangle inequality above to operate more quickly. In general, for any c > 0, where d is the number of dimensions in the Euclidean space, there is a polynomial-time algorithm that finds a tour of length at most (1 + 1/c) times the optimal for geometric instances of TSP in time; this is called a polynomial-time approximation scheme (PTAS).

Keywords- metric, minimum spanning, dimensions, polynomial-time

Unique Identification Number - IJEDR1704013
Page Number(s) - 81-83
Pubished in - Volume 5 | Issue 4 | October 2017
DOI (Digital Object Identifier) -   
Publisher - IJEDR (ISSN - 2321-9939)

  Monika Yadav,  Dr. Ashutosh,   "Study on Euclidian TSP and asymmetric TSP with reference to graph theory", International Journal of Engineering Development and Research (IJEDR), ISSN:2321-9939, Volume.5, Issue 4, pp.81-83, October 2017, Available at :http://www.ijedr.org/papers/IJEDR1704013.pdf