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 n^c-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.

• Optimal Parallel Construction of Hamiltonian Cycles and Spanning Trees in Random Graphs gives ultrafast PRAM algorithms for similar graph problems.
  
• Here is a whimsical explanation of parallel computing, a tutorial on parallel computing, and a list of parallel computing resources
  
• Here is an overview of our work in parallel computing and relevant papers.

Copyright © 2015-2017 Quentin F. Stout