Many classical graph problems have efficient sequential algorithms, with some of them even running in linear time in the input size, which is best possible. But linear time is not fast enough for massive datasets, for which we turn to concurrency.

We study concurrent algorithms for the most fundamental graph problem:  the connected components of an undirected graph. This problem has been extensively studied in the concurrent setting, especially on the classical Parallel Random Access Machines (PRAM). However, many fast PRAM algorithms are hard to implement due to the complications in the algorithms.

Our first result is several new elegant PRAM algorithms for the connected components problem, which achieve the same time complexity comparing to the existing best ones but are significantly simpler. Our algorithms are deterministic, use linear number of processors, and run in O(log n) time. This is joint work with Robert Tarjan.

Our second result is a simple PRAM algorithm for connected components and spanning forest that runs faster than any existing ones when the input graph has small diameter, which is usually the case in real-world applications. The algorithm is randomized, uses linear number of processors, and runs in O(log d loglog n) time with high probability where d is the diameter of the input graph. This is joint work with Robert Tarjan and Peilin Zhong.

Sixue Liu is a PhD student in Computer Science at Princeton University, advised by Robert Tarjan. He obtains a master degree from Institute for Interdisciplinary Information Sciences, Tsinghua University. His main research interests are Algorithm Design and Fine-Grained Complexity.