SOLVING THE TRAVELING SALESMAN PROBLEM USING EFFICIENT RANDOMIZED PARALLEL APPROXIMATION ALGORITHMS

References

• Aho , A. V. , Hopcroft , J. E. and Ullman , J. D. , ( 1974 ). The Design and Analysis of Computer Algorithms , (Addison-Wesley) .
   Google Scholar
• Atallah , M. and Vishkin , U. , ( 1984 ), Finding Euler tours in parallel , J. Comput. Syst. Sci. , 29 , 330 – 337 .
   Web of Science ®Google Scholar
• Chin , F. Y. , Lam , J. and Chen , I.-N. , ( 1982 ). Efficient parallel algorithms for some graph problems , Commun. ACM , 25 , 659 – 665 .
   Google Scholar
• Christofides , N. , ( 1976 ). Worst-case analysis of a new heuristic for the travelling salesman problem , Report 388, Graduate School of Industrial Administration , Carnegie-Mellon University , Pittsburgh , LS .
   Google Scholar
• Cornuéjols , G. and Nemhauser , G. L. , ( 1978 ). Tight bound for Christofides' traveling salesman heuristic , Math. Program. , 14 , 116 – 121 .
   Web of Science ®Google Scholar
• Held , M. and Karp , R. M. , ( 1962 ). A dynamic programming approach to sequencing problems , SIAM J. Appl. Math. 10 , 196 – 210 .
   Web of Science ®Google Scholar
• Itai , A. , Papadimitriou , C. H. , and Szwarefiter , J. , ( 1982 ). Hamiltonian paths in grid graphs , SIAM J. Comput. , 11 , 676 – 686 .
   Web of Science ®Google Scholar
• JáJá , J. , ( 1992 ). An Introduction to Parallel Algorithms , (Addison-Wesley) .
   Google Scholar
• Karloff , H. J. , ( 1986 ), A Las Vegas RNC algorithm for maximum matching , Combinatorica 6 , 387 – 391 .
   Google Scholar
• Lawler , E. L. , Lenstra , J. K. , Rinnooy Kan , A. H. G. and Shmoys , D. B. eds., ( 1985 ). The Traveling Salesman Problem - A Guided Tour of Combinatorial Optimization , (John Wiley & Sons) .
   Google Scholar
• Lin , S. and Kernighan , B. W. , ( 1973 ). An effective heuristic algorithm for the traveling salesman problem , Oper. Res. , 21 , 498 – 516 .
   Web of Science ®Google Scholar
• Little , J. D. C. , Murty , K. G. , Sweeney , D. W. and Karel , C. , ( 1963 ). An algorithm for the traveling salesman problem , Oper. Res. 11 , 972 – 989 .
   Web of Science ®Google Scholar
• Mohan , J. , Experience with two parallel programs solving the traveling salesman problem , Proc. of 1983 Int'l Conf. on Parallel Processing , 191 – 193 .
   Google Scholar
• Mulmuley , K. , Vazirani , U. and Vazirani , V. , (1987). Matching is as easy as matrix inversion, Combinaiorica , 7, 105–113.
   Web of Science ®Google Scholar
• Nath , D. and Maheshwari , S. N. , ( 1982 ). Parallel algorithms for the connected components and minimal spanning trees, Inf. Process. Lett. , 14 , 7 – 11 .
   Google Scholar
• Papadimitriou , C. H. and Steiglitz , K. , ( 1977 ). “On the complexity of local search for the traveling salesman problem” , SIAM J. Comput. 6 , 76 – 83 .
   Google Scholar
• Papadimitriou , C. H. and Steiglitz , K. , ( 1982 ). Combinatorial Optimization Algorithms and Complexity , Prentice-Hall .
   Google Scholar
• Quinn , M. J. , ( 1990 ). Analysis and implementation of branch-and-bound algorithms on a hypercube multicomputer , IEEE Trans. Comput. , 39 , 384 – 387 .
   Google Scholar
• Quinn , M. J. and Deo , N. , ( 1984 ), Parallel Graph Algorithms , ACM Comput. Surv. , 16 , 319 – 348 .
   Web of Science ®Google Scholar
• Rosenkrantz , D. J. , Stearns , R. E. , Lewis II , P. M. , ( 1977 ). An analysis of several heuristics for the traveling salesman problem , SIAM J. Comput. , 6 , 563 – 581 .
   Google Scholar
• Sahni , S. and Gonzalez , T. , ( 1976 ). P-complete approximation problems , J. ACM , 23 , 555 – 565 .
   Web of Science ®Google Scholar
• Tarjan , R. E. , ( 1983 ). Data Structures and Network Algorithms , SIAM , Philadelphia , PA .
   Google Scholar
• Tarjan , R. E. and Vishkin , U. , ( 1985 ). An efficient parallel biconnectivity algorithm , SIAM J. Comput. 14 , 862 – 874 .
   Web of Science ®Google Scholar