O'Reilly logo

Algorithms and Parallel Computing by Fayez Gebali

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

8.7 USEFUL THEOREMS

We show in this section some useful theorems related to the formal technique we proposed in the previous section. The following theorem discusses how we can check if a given algorithm is cycle free or not.

Theorem 8.1

An algorithm with W nodes/tasks is cycle free if and only if Ak has zeros in its main diagonal elements for 1 k W.

Proof:

Assume the algorithm is cycle free. In that case, we do not expect any diagonal element to be nonzero for Ak with k ≥ 1. The worst case situation is when our algorithm has all the nodes connected in one long string of W nodes as shown in Fig. 8.5a. The highest power for Ak is when k = W − 1 since this is the maximum length of the path between W nodes. AW = 0 since there is no path of length W. Thus, a cycle-free algorithm will produce zero diagonal elements for all powers of Ak with 1 ≤ kW.

Figure 8.5 Worst case algorithm that has 10 nodes. (a) When the algorithm is cycle free. (b) The longest possible cycle in an algorithm with 10 nodes is 10.

c08f005

Now assume that all powers of Ak for 1 ≤ kW are all zero diagonal elements. This proves that we do not have any cycles of length 1 to W in the algorithm. This proves that the algorithm does not have any cycles since for W nodes, we cannot have a cycle of length greater than W. Figure 8.5b shows the longest possible cycle in an algorithm of W nodes/tasks.

The following ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required