Speaker: Mikkel Thorup
Title: Planning for fast connectivity updates
Abstract:
Understanding how a single edge deletion can affect the connectivity
of a graph amounts to finding the graph bridges. But when faced with
d>1 deletions, can we establish as easily how the connectivity
changes? When planning for an emergency, we want to understand the
structure of our network ahead of time, and respond swiftly when an
emergency actually happens.
We describe a linear-space representation of graphs which enables us
to determine how a batch of edge updates can impact the graph. Given
a set of d edge updates, in time O(d polylog n) we can obtain the
number of connected components, the size of each component, and a
fast oracle for answering connectivity queries in the updated graph.
The initial representation is polynomial-time constructible.
This is joint work Mihai Partrascu (MIT). An exteded abstract is to
be found in Proc. FOCS'07.