Concurrent Connected Components

Cette conférence est coorganisée avec l'IRIF (CNRS et université Paris-Diderot) et fait partie du cycle d'exposés « IRIF Distinguished Talks ».

Résumé

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.