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.