Philip D. MacKenzie and
Quentin F. Stout

EECS Department, University of Michigan

**Abstract:**
We give tight bounds on the parallel complexity of some problems involving
random graphs.
Specifically,
we show that a Hamiltonian cycle, a breadth first spanning tree, and a maximal
matching can all be constructed
in Θ(log^{*} *n*) expected time using
*n* /log^{*}(*n*) processors
on the CRCW PRAM.
This is a substantial improvement over the
best previous algorithms, which required
Θ((loglog *n*)^{2}) time and
*n* log^{2}(*n*) processors.

We then introduce a technique which allows us to
prove that constructing an edge cover
of a random graph from its adjacency matrix
requires Ω(log^{*} *n*) expected time on a CRCW PRAM with
O(*n*) processors.
Constructing an edge cover is implicit in constructing a spanning tree,
a Hamiltonian cycle, and a maximal matching, so
this lower bound holds for all these problems, showing that our
algorithms are optimal.
This new lower bound technique is one of the very few lower
bound techniques known
which apply to randomized CRCW PRAM algorithms, and it provides
the first nontrivial parallel lower bound for these
problems. Notice that we simultaneously achieve the minimum time possible
and linear speedup.

The lower bound proof is based on a simple analogue,
which we call the *Parallel Target Shooting* problem.
Imagine that there are
*n* targets and *n* shooters. Each time a shooter shoots at
a target, there is a fixed probability *p*, 0 < *p* < 1, that
the shooter misses. This probability is independent of any other shots.
The goal is to hit all of the targets at least once. Shooters shoot
at targets in rounds, and between each round the results are observed
and then it is decided how to reallocate shooters for the next round.
More than one shooter can be shooting at a target in a given round.

This is relevant to finding an edge cover because the processors have to search the adjacency table to find at least one edge per vertex. What is much less clear is how the PRAM can attain this time, since to just count the number of unhit targets takes Ω(log

Question:What is the minimal expected number of rounds needed until all targets are hit?

Answer:Ω(log^{*}n), which can be obtained if in each round the shooters are allocated as evenly as possible to the targets still unhit.

**Keywords:**
random graph, CRCW PRAM, parallel graph algorithm, edge cover,
lower bounds, parallel target shooting, graph theory, SIMD shared memory
parallel computer

Complete paper
This paper
appears in *Proc. 5th ACM Symp. on Parallel Algorithms and Architectures*
(1993), pp. 224-229.

- Parallel computing:
- An overview
of my work in this area, and my
papers.

Here is a somewhat whimsical explanation of parallel computing, a tutorial on parallel computing and a list of parallel computing resources - Ultrafast PRAM algorithms:
- Ultrafast Parallel Algorithms and Reconfigurable Meshes surveys some of our work in this area. Sub-logarithmic algorithms for geometric problems appear in Constant-Time Geometry on PRAMs and Ultra-Fast Expected Time Algorithms

Copyright © 2005-2020 Quentin F. Stout |