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-2018 Quentin F. Stout.