TY  - BOOK
AU  - Hoda Ahmed Darwish 
AU  - Ihab Elsayed Talkhan  , 
TI  - Reduced Complexity Divide and Conquer Algorithm for Large Scale TSP / 
PY  - 2014///
CY  - Cairo : 
PB  - Hoda Ahmed Darwish  , 
KW  - Computational Geometry
KW  - Heuristic Algorithms
KW  - Traveling Salesman Problem
N1  - Thesis (M.Sc.) - Cairo University - Faculty of Engineering - Department of Computer Engineering; Issued also as CD
N2  - This thesis presents an algorithm to solve the NP-hard Traveling Salesman Problem (TSP) problem of finding the shortest path passing through all given cities while only passing by each city once and finishing at the same starting city.  It is based on the idea of utilizing a spatial 2geographical3 Divide and Conquer technique in conjunction with heuristic Nearest Neighbor 2-opt TSP algorithm. At a cost of only 9% lower performance, the algorithm has complexity of O((N/{u221A}b)2) where N is the number of cities and b is the number of spatial divisions. This is much lower than  published results.  Specifically it is lower  than the reference Lin-Kernighan algorithm which has computational complexity of O (N2.2)making it practical for real applications
UR  - http://172.23.153.220/th.pdf
ER  -