We study minimizing the communication cost in parallel algorithm designs, by minimizing the number of communication phases in coarse-grained parallel computers. There have been several recent 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 sub problems 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.