Graph algorithms with small communication costs

We study minimizing communication cost in parallel algorithm design, by min imizing the number of communication phases in coarse-grained parallel compu ters. There have been several recent papers dealing with parallel algorithm s of small communication cost under different models. Most of these results are for computational geometry problems. For these problems it has been po ssible to decompose tasks into appropriate subproblems in a communication-e fficient way. It appears to be somewhat more difficult to design parallel a lgorithms with small communication phases for graph theory problems. In thi s paper we focus on the design of deterministic algorithms with a small num ber of communication phases for the list ranking problem and the shortest p ath problem.