Parallel Graph Contraction
Abstract
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 + e)/lg n processors reduces a connected n-node e-edge graph to a single node in O(lg squared n) steps and a second simple algorithm which uses the first as a subroutine.
Document Details
- Document Type
- Technical Report
- Publication Date
- May 01, 1989
- Accession Number
- ADA211916
Entities
People
- Cynthia A. Phillips
Organizations
- Massachusetts Institute of Technology