| Proving the optimality of algorithms for important combinatorial problems and determining their intrinsic hardness properties requires finding strong lower bounds for them.; The model of computation we consider is the PRAM without bit operations. The model eliminates those operations that allow bit-extraction or updates of the bits of the individual registers, but provides the usual arithmetic, indirect referencing, conditional and unconditional branch operations at unit cost. We consider here an unbounded fan-in model, in which the operations {lcub}+, min, max{rcub} can have unbounded fan-in at unit cost.; We show that computing the shortest path between two specified vertices in a weighted graph on n vertices cannot be solved in o(log n) time on an unbounded fan-in PRAM without bit operations using nΩ(1) processors, even when the bit-lengths of the weights on the edges are restricted to be of size o(log3 n). This shows that the matrix repeated-squaring algorithm for the SHORTEST PATH PROBLEM is optimal in the unbounded fan-in PRAM model without bit operations.; We also show that computing the maximum blocking flow (or equivalently, the maximum flow in a directed acyclic graph) cannot be computed in time o(n1/4) using 2Ω( n1/4) processors in the same model, even when the inputs are restricted to be of length O(n 2).; The lower bounds also hold (with slightly weaker parameters) in the case of randomized algorithms with two-sided error, and even when the running time of the algorithm is allowed to depend on the total bit-length.; The thesis also provides lower bounds for other restricted cases of these problems which are useful in practice. We also obtain as a corollary a weak lower bound on the problem of computing weighted matchings in bipartite graphs which is not known to have a fast parallel algorithm. |
