Tree-Based Graph Algorithms for Some Parallel Computers.
Quentin F. Stout · Proceedings of the International Conference on Parallel Processing · 1985
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. By using edges, instead of requiring an entire adjacency matrix, these algorithms use only time on a 2-dimensional mesh, instead of the time required with matrix input. Further, the edge-based algorithms extend naturally to meshes of arbitrary dimension ,fi nishing in time. All of the times are optimal, and the algorithms extend to VLSI and pyramid models.