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.
Short bio: Robert E. Tarjan is the Distinguished University Professor of Computer Science at Princeton University and Chief Scientist of Intertrust Technologies. He received his B.S. from the California Institute of Technology in 1969 and his M. S. and Ph.D. from Stanford University in 1971 and 1972. He has held academic positions at Cornell, Berkeley, Stanford, and NYU, and industrial research positions at Bell Labs, NEC, HP, and Microsoft. Among other honors, he received the Nevanlina Prize in Informatics, given by the International Mathematical Union, in 1982, the A.C.M. Turing Award in 1986, and the A. C. M. Paris Kanellakis Award in Theory and Practice in 1999, the last together with Daniel Sleator for their invention of splay trees. He is a member of the National Academy of Sciences and the National Academy of Engineering, and a Fellow of the American Philosophical Society and the American Academy of Arts and Sciences. He has published over 250 papers, mostly in the areas of the design and analysis of data structures and graph and network algorithms. In 2018 he was named one of the “50 Most Influential Living Computer Scientists” by TheBestSchools.org.
