Quentin F. Stout

Computer Science and Engineering, University of Michigan

**Abstract:**
This paper gives several optimal mesh computer, VLSI, and pyramid computer
algorithms for determining properties of an arbitrary undirected graph,
where the graph is given as an unordered collection of edges.
The algorithms first find spanning trees and then use them to determine
properties of the graph.
For a graph with e edges and v vertices,
by using a list of edges, instead of requiring an entire adjacency matrix, these
algorithms use only Θ(e^{1/2})
time on a 2-dimensional mesh, instead of the Ω(v) time required
with matrix input.
Further, the edge-based algorithms extend naturally to meshes of arbitrary
dimension *d*, finishing in Θ(e^{1/d}) time.
All of the times are optimal, and the algorithms extend to VLSI and pyramid
models.

**Keywords:**
parallel computer,
parallel graph algorithms, component labeling, unordered edge
input, spanning forest, descendant functions, ancestor functions, preorder,
postorder, mesh-connected computer

**Complete paper.**
This paper appears in
*Proc. 1985 International Conference on Parallel Processing*,
pp. 727-730.

- Much of the content of this paper has been incorporated into the book R Miller and QF Stout, Parallel Algorithms for Regular Architectures: Meshes and Pyramids, MIT Press, 1996.
- My papers in parallel computing, and an overview of my research
- A modest explanation of parallel computing, a tutorial, Parallel Computing 101, and a list of parallel computing resources

Copyright © 2005-2017 Quentin F. Stout. |