Improving the Performance of Approximation Algorithm to Solve Travelling Salesman Problem Using Parallel Algorithm

Travelling salesman problem is a NP complete problem and can be solved using approximation algorithm. It is a minimization problem starting and finishing at a specified vertex after having visited each other vertex exactly once. Often, the model is a complete graph. An algorithm that returns near-optimal solutions is called approximation algorithms. Through analyzing the Metric TSP the performance of approximation algorithm can be improved significantly using graphical analysis of spanning trees and depth first search and implementing a parallel algorithm/program to find a path with approximately minimum travelling cost.