Generating permutations and finding Hamiltonian Paths

How can we parallelize this particular algorithm? Recall that combinations of starting and ending nodes were generated prior to generating the permutations. Since the number of processors that we have available are limited, just breaking down the combinations of the starting and ending nodes would be sufficient.

What's tricky in breaking down the jobs is in the order that the programs can handle in visiting different starting and ending nodes. In this particular instance, the program broke them down like this:

for int i=1; i<=|V|; i++
   for int j=1; j<i; j++
      generate permutations without i and j and compute output
   end for
end for

How can we equally divide these induces equally? Let i be the starting node and j be the ending node. However, the code would not know which i and j to start and to stop. so we introduce the notion of k-indexing where k is the kth combination using i and j. to express k in terms of i and j:
k = (i-1)*(i-2)/2 + j;
also, just ith index can be traced using the findi function. the jth index we'll just subtract the k value at the desired index with the (i-1)*(i-2)/2+1 which i is the ith row in question first, each processors are subject to completing the same number of jobs for simplicity, but the processors which satisfys if(totalCombnamely, kth index of totalComb-processorId or corresponding i,jth index

With no extra communication required for each processor other than starting up processes and cleaning up, the result, graphed in figure 3.6 shows an expected result although there are still some loss of time from a strictly linear running time.

Figure 3.6: Result of running time versus # procs used with 12 noded graph