Parallel Algorithm
- Sequence of square operations.
- Each square op. contains n3 independent (min,+) operations
that can be performed in parallel yielding n3 results.
- Each of the n2 entries D(i,j) is a minimum of n values.
- Complexity:
- log n square computations.
- 1 time step for all (min,+) operations.
- log n time to compute each of the n2 minimums.
Parallel complexity O(log2 n)
Author: Wolfgang Schreiner
Last Modification: October 13, 1997