SEARCHING FOR BACKBONES - AN EFFICIENT PARALLEL ALGORITHM FOR THE TRAVELING SALESMAN PROBLEM

The Traveling Salesman Problem (TSP) plays an important role in Operat ions Research, Applied Mathematics and Computational Physics. We inves tigated it using a stochastic approach. Studying several solutions of a special TSP we found that many parts of a good solution are the same in all other good solutions for this problem. In this paper we discus s an efficient parallel method to reduce the TSP to a smaller one by f inding these backbones and eliminating them to get even better solutio ns in a very short time and a few observables of interest correspondin g to this parallel approach.