Time-optimal parallel algorithm for finding minimum spanning trees without concurrent write

spanning trees of weighted undirected graphs can be found in $O(\log n)$
time using a polynomial number of processors. We present the
first deterministic time-optimal algorithm for finding minimum
spanning trees without using concurrent write on the PRAM models. The
algorithm takes $O(\log n)$ time using a polynomial number of EREW
processors. This is the first parallel algorithm that solves a
non-trivial graph problem in $O(\log n)$ time without using concurrent
write or randomization. The time complexity of the algorithm matches
the time bound of the best algorithm running on the CRCW PRAM. Our
result also implies that problems like connected components,
biconnectivity and ear decomposition can also be solved in $O(\log n)$
time without the power of concurrent write. The best previous known
result for this problem runs in $O(\log n \loglog n)$ time on the EREW
PRAM.



Joint work with Yijie Han.