Sublinear-Time Sampling of Spanning Trees in the Congested Clique

Sriram V. Pemmaraju, Sourya Roy, Joshua Z. Sobel

We present the first sublinear-in-$n$ round algorithm for sampling an approximately uniform spanning tree of an $n$-vertex graph in the CongestedClique model of distributed computi…