TSP en procesamiento paralelo

TSP es el típico problema en grafos: Travel salesman problem, o el problema del agente viajero.
En un computador tradicional:
La típica solución exhaustiva, es, probar todos los nodos contra todos los nodos (ciudades).
Si se tienen N ciudades, se tienen N*(N-1)*...4*3*2 probabilidades de rutas, de las cuales, en la exhaustiva, se encuentra la respuesta óptima.
La típica solución usando algoritmos genéticos, es hacer que el fenotipo contenga una ruta, y la función fitness sea la menor distancia posible... ahí, aplicar mutación y cruzamiento, etc...

En un computador paralelo, si no me equivoco, podríamos hacer esto:
Hacer que cada nodo-procesador represente una ciudad;
A continuación, cada uno calcule la distancia al resto de ciudades [O(n) para cada procesador]
Cada uno calcule la menor distancia a otra ciudad (Como el pár más próximo, pero con una sola ciudad)
Mandar esa solución al nodo-procesador principal;
Ahí verifica las mejores puntuaciones, las repetidas las almacena; las otras, las manda a corregir.
Y así así, hasta que acabe...
Complejidad total: O(n*log(n) )

Parece sencillo, no?
Corríjanme si me equivoco :)