Parallel Graph Contraction

The parallel tree contraction technique of Miller and Reif has proved to be a valuable tool in many parallel graph algorithms. This paper provides a similar contraction technique that applies not only to trees, but also to general graphs. It also provides a second, potentially faster contraction techniques for bounded-degree graphs and general graphs when an embedding is known. In this paper, we use the technique of parallel contraction in a more general setting. We show that a remarkably simple contraction algorithm that uses n elg n processors reduces a connected n-node e-edge graph to a single node in Olg squared n steps and a second simple algorithm which uses the first as a subroutine.