Graph algorithms with small communication costs

Studies minimizing the communication cost in parallel algorithm design by minimizing the number of communication phases in coarse-grained parallel computers. There have been several papers dealing with parallel algorithms of small communication cost under different models. Most of these results are for computational geometry problems. For these problems, it has been possible to decompose tasks into appropriate subproblems in a communication-efficient way. It appears to be somewhat more difficult to design parallel algorithms with small communication phases for graph theory problems. In this paper, we focus on the design of deterministic algorithms with a small number of communication phases for the list-ranking problem and the shortest-path problem. We also discuss empirical experimental results justifying this design goal, especially for implementations on networks of workstations