TY  - JOUR
AU  - Gurke, Renate
TI  - The approximate solution of the Euclidean traveling salesman problem on a CRAY X-MP
JO  - Parallel computing
VL  - 8
IS  - 1-3
SN  - 0167-8191
CY  - Amsterdam [u.a.]
PB  - North-Holland, Elsevier Science
M1  - FZJ-2016-03693
SP  - 177 - 183
PY  - 1988
AB  - 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.
LB  - PUB:(DE-HGF)16
UR  - <Go to ISI:>//WOS:A1988R035300019
DO  - DOI:10.1016/0167-8191(88)90122-6
UR  - https://juser.fz-juelich.de/record/811184
ER  -