Please use this identifier to cite or link to this item: http://arks.princeton.edu/ark:/88435/dsp010r967677z
 Title: Simple Parallel Randomized Connected Components Algorithms Authors: Zlatin, Eitan Advisors: Tarjan, Robert Department: Computer Science Class Year: 2020 Abstract: We study three simple algorithms for concurrently computing connected components in a randomized setting, A, S and P. These algorithms were previously studied in a deterministic setting by Liu and Tarjan, who provided an $O(\log^2 n)$ step bound for A and S, with P remaining unanalyzed.\footnote{We use $\log$ to denote the base two logarithm} In a randomized setting, we provide $O(\log n)$ and $O(\log n \log \log n)$ step bounds for A and S respectively, and a $O(\frac{\log^2 n}{\log \log n})$ bound for P. All results hold with high probability. URI: http://arks.princeton.edu/ark:/88435/dsp010r967677z Type of Material: Princeton University Senior Theses Language: en Appears in Collections: Computer Science, 1988-2020