Skip navigation
Please use this identifier to cite or link to this item:
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.
Type of Material: Princeton University Senior Theses
Language: en
Appears in Collections:Computer Science, 1988-2020

Files in This Item:
File Description SizeFormat 
ZLATIN-EITAN-THESIS.pdf255.38 kBAdobe PDF    Request a copy

Items in Dataspace are protected by copyright, with all rights reserved, unless otherwise indicated.