%0 Journal Article
%A Gurke, Renate
%T The approximate solution of the Euclidean traveling salesman problem on a CRAY X-MP
%J Parallel computing
%V 8
%N 1-3
%@ 0167-8191
%C Amsterdam [u.a.]
%I North-Holland, Elsevier Science
%M FZJ-2016-03693
%P 177 - 183
%D 1988
%X The efficient use of MIMD computers calls for a careful choice of adequate algorithms as for an implementation taking into account the particular architecture. To demonstrate these facts, a parallel algorithm to find an approximate solution to the Euclidean Traveling Salesman Problem (ETSP) is presented. The algorithm is a parallelization of Karp's partitioning algorithm. It is a divide-and-conquer method for solving the ETSP approximately. Since the successor vertex to any vertex in the tour is usually a nearby vertex, the problem can be ‘geographically’ partitioned into subproblems which then can be solved independently. The resulting subtours can be combined into a single tour which is an approximate solution to the ETSP. The algorithm is implemented on a CRAY X-MP with two and four processors, and results using macrotasking and microtasking are presented.
%F PUB:(DE-HGF)16
%9 Journal Article
%U <Go to ISI:>//WOS:A1988R035300019
%R 10.1016/0167-8191(88)90122-6
%U https://juser.fz-juelich.de/record/811184