Ultrafast Graph Algorithms on Reconfigurable Meshes

Douglas M. Van Wieren   and   Quentin F. Stout
Computer Science and Engineering
University of Michigan


Abstract: We present some graph algorithms taking Θ(log* n) expected time for random graphs. The parallel computing model used is the "mesh with row and column subbuses", RCS-mesh. This is a modestly reconfigurable model that was implemented as part of the MasPar MP series of machines. The algorithms can also be directly implemented on the more power reconfigurable mesh (rmesh).

We show that an nxn RCS-mesh can find a Hamiltonian cycle, or determine that none exists, on a random graph G of n vertices, where the adjacency matrix of G is stored one entry per processor, in Θ(log* n) expected time. Further, in the same time bounds it can label the vertices in the order in which they appear in the Hamiltonian cycle. The existence of other substructures, such as a d-dimensional torus or a complete binary tree, can be decided in the same time bounds. Further, for any 0 < c <1, in only constant expected time one can determine if G is strongly nc-connected.

Keywords: parallel algorithm, random graph, Hamiltonican cycle, reconfigurable mesh, rmesh, RCS-mesh

Complete paper.   This paper appears in Proc. 2nd Workshop on Reconfigurable Architectures (1995), pp. 1-13. It is a preliminary version, but we never wrote up a more detailed one.


Related Work:

Quentin's Home Copyright © 2015-2017 Quentin F. Stout