Tree-based Graph Algorithms for Some Parallel Computers

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 Θ(e1/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 Θ(e1/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.


Related Work:

Quentin's Home Copyright © 2005-2018 Quentin F. Stout.