NC and RNC Algorithms for the Uniform Generation
-----------------------------------------
of Paths and Trees in Graphs
----------------------------
Ida Pu, Michele Zito, Martyn Amos and Alan Gibbons
Department of Computer Science, University of Warwick
We outline a number of deterministic and randomised parallel
algorithms for the uniform generation of variously defined
paths and for the uniform generation of spanning trees of a
graph. The algorithms run in low-order polylogarithmic time and
involve a polynomial amount work. These are essentially the
first efficient parallel algorithms described for
these problems.