\begin{itemize}

	\item Question: Construct a parallel Traveling Salesman
	Algorithm.  What is it's complexity?

	\item Answer:
	There will be a processor for each edge, each vertex, and a
	Collector to Collect all the edges in the solution.	
	\begin{enumerate}
	\item The processes for each edge will have the following code:
	\begin{verbatim}
	edge(){
	   int junk, yes, count = 0;

	   for(;;){
	      if(iprobe(TAKE)){
	         receive(TAKE,&junk));
	         send(Collector,ADDME,junk);
	         receive(OK,&yes);
	         if(yes){
	            send(vertex_a,INC_TAKEN,junk);
	            send(vertex_b,INC_TAKEN,junk);
	         }else{
	            send(vertex_a,DELETE,junk);
	            send(vertex_b,DELETE,junk);
	         }
	      }
	      if(iprobe(REMOVE)){
	         receive(REMOVE,&junk)
	         send(vertex_a,DELETE,junk);
	         send(vertex_b,DELETE,junk);
	      }
	      if(iprobe(POSSIBLY_TAKE)){
	         receive(POSSIBLY_TAKE,&junk)
	         count++;
	         if(count == 2){
	            send(Collector,ADDME,junk);
	            receive(OK,&yes);
	            if(yes){
	               send(vertex_a,INC_TAKEN,junk);
	               send(vertex_b,INC_TAKEN,junk);
	            }else{
	               send(vertex_a,DELETE,junk);
	               send(vertex_b,DELETE,junk);
	            }
	         }
	      } /* POSSIBLY_TAKE */
	   } /* for */
	} /* edge */
	\end{verbatim}
\newpage
	\item The processes for each vertex will have the following code:
	\begin{verbatim}
	/* edges in Adjacency list are in sorted order (cheap to expensive) */
	vertex(){
	   int junk, taken=0, cheapest_edge;

	   cheapest_edge = first_edge_in_adjacency_list;
	   send(cheapest_edge,POSSIBLY_TAKE,junk);
	   for(;;){
	      if(iprobe(INC_TAKE)){
	         receive(INC_TAKE,&junk);
	         taken++;
	         remove_edge_from_adjacency_list(from());
	         if(taken==2){
	            for(each_edge_in_adjacency_list)
	               send(edge,REMOVE,junk);
	         }
	      }
	      if(iprobe(DELETE)){
	         receive(DELETE,&junk);
	         remove_edge_from_adjacency_list(from());
	         if(from() == cheapest_edge){
	            cheapest_edge = first_edge_in_adjacency_list;
	            send(cheapest_edge,POSSIBLY_TAKE,junk);
	         }
	      }
	      if(((length(Adjacency_List)==2) && (taken==0)) || 
	         ((length(Adjacency_List)==1) && (taken==1)))
	            for(each_edge_in_adjacency_list)
	               send(edge,TAKE,junk);
	      if(taken==2)
	         for(each_edge_in_adjacency_list)
	            send(edge,REMOVE,junk);
	      if((length(Adjacency_List) + taken) < 2)
	         ERROR();
	\end{verbatim}	
\newpage
	\item The Collector will have the following code:
	\begin{verbatim}
	collector(){
	   int junk, edges;

	   for(edges=0;edges<N;){
	      receive(ADDME, &junk);
	         if(check_cycle_too_early(from()))
	            send(from(),OK,FALSE);
	         else
	            Add_edge_to_List(from());
	            send(from(),OK,TRUE);
	   }
	   Output_Edges_In_Solution();
	}
	\end{verbatim}
	\end{enumerate}

	Therefore, there will be $n^{2}+n+1$ processors (maximum).

	Since this is a known NP-Complete Problem, I had better not say
	that this is anything but an exponential algorithm,....

	Except for it's call to Collector, Edge is a constant time
	"function".  Collector's time is spent in
	\verb+check_cycle_too_early()+, and may (in worst case) have to check
	this for every edge in the graph.

	The problem with this is the fact that it is the same as the
	greedy algorithm for the TSP, and there are cases where it does
	not come up with the optimal solution, just a good one that is
	very close to optimal.  

\end{itemize}
