Concurrent Connected Components

This conference is co-organized with IRIF (CNRS and Université Paris-Diderot) and is part of the " IRIF Distinguished Talks " series.

Abstract

Finding the connected components of a graph is one of the most basic graph problems. Although it is easy to find components sequentially using graph search or a disjoint set union algorithm, some important applications require finding the components of huge graphs, making sequential algorithms too slow. We describe recent progress on concurrent algorithms for this problem. Some simple algorithms seem surprisingly hard to analyze, and claims made in the literature about some of them are false.