External Connected Components

application, but it turned out to be particularly suited for
external computation. This idea can, with little modification,
be reused for computing the connected components of a graph.
List ranking now shows to have been a lucky case: this new
algorithm may lead to a good paralel algorithm if the graphs
are very sparse but not in general. However, in the external
case it performs amazingly. For a graph with m nodes and n edges
(assuming the usual things and an input that is given as a set
of m pairs of two indices) only 7 * m + 4 * n integers have to
be read and written. This is the time that appears from
experiments, we can prove only something with an additional
log-factor.

The presentation will be informal, possibly without sheets.