Campus Event Calendar

Event Entry

What and Who

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

Ka Wong Chong
Max-Planck-Institut für Informatik
AG1 Mittagsseminar
AG 1  
AG Audience

Date, Time and Location

Monday, 19 January 98
60 Minutes


It has been known for a long time that on the CRCW PRAM, minimum

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

Joint work with Yijie Han.


Ka Wong Chong
0681/9325 124
--email hidden
passcode not visible
logged in users only

Tags, Category, Keywords and additional notes

parallel algorithms, PRAM, minimum spanning trees, connected components