Campus Event Calendar

Event Entry

New for: D1

What and Who

External Connected Components

Jop Sibeyn
Max-Planck-Institut für Informatik - AG 1
AG1 Mittagsseminar (own work)
AG 1  
AG Audience
-- Not specified --

Date, Time and Location

Monday, 21 December 98
-- Not specified --


An earlier idea for list ranking was good for parallel

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

The presentation will be informal, possibly without sheets.


Jop F. Sibeyn
--email hidden
passcode not visible
logged in users only