Finding connected components in massive graphs

Abstract

Finding connected components is a fundamental problem in algorithmic graph theory.  Analysis of big data sets requires solving this problem on massive graphs.  On such graphs, sequential algorithms are much too slow.  We describe two classes of fast algorithms that rely on massive concurrency.  Though simple, verifying that these algorithms are both correct and efficient requires careful and subtle analysis.

Short Bio

Prof. Robert E. Tarjan obtained a Bachelor's degree in mathematics from the California Institute of Technology in 1969. At Stanford University, he received his master's degree in computer science in 1971 and a Ph.D. in computer science (with a minor in mathematics), supervised by Robert Floyd and Donald Knuth in 1972.

Prof. Tarjan is currently the James S. McDonnell Distinguished University Professor of Computer Science at Princeton University.  He has also held academic positions at Cornell University (1972–73), University of California, Berkeley (1973–1975), Stanford University (1974–1980), and New York University (1981–1985). He has also been a fellow of the NEC Research Institute (1989–1997). In April 2013 he joined Microsoft Research Silicon Valley in addition to the position at Princeton. In October 2014 he rejoined Intertrust Technologies as chief scientist. Prof. Tarjan has worked at AT&T Bell Labs (1980–1989), Intertrust Technologies (1997–2001, 2014–2022), Compaq (2002) and Hewlett Packard (2006–2013).

Prof. Tarjan received the Turing Award jointly with John Hopcroft in 1986 "for fundamental achievements in the design and analysis of algorithms and data structures". Some of the other awards for Prof. Tarjan include:
Nevanlinna Prize in Information Science (1983)
Member of the American Academy of Arts and Sciences, elected 1985
National Academy of Sciences Award for Initiatives in Research (1984)
Member of the National Academy of Sciences, elected 1987
Member of the National Academy of Engineering, elected 1988
Member of the American Philosophical Society, elected 1990
Paris Kanellakis Award in Theory and Practice, ACM (1999)
Caltech Distinguished Alumni Award, California Institute of Technology (2010)