CS 269S, Fall 2013: Theory Seminar
Bren Hall, Room 1422, 1pm
November 8, 2013:

Dynamic graph connectivity in polylogarithmic worst case time

by Bruce M. Kapron, Valerie King, and Ben Mountjoy

Appeared in SODA 2013

Presented by Jack Cheng

The dynamic graph connectivity problem is the following: given a graph on a fixed set of n nodes which is undergoing a sequence of edge insertions and deletions, answer queries of the form q(a, b): .Is there a path between nodes a and b?. While data structures for this problem with polylogarithmic amortized time per operation have been known since the mid-1990.s, these data structures have .(n) worst case time. In fact, no previously known solution has worst case time per operation which is o(sqrt(n)).

We present a solution with worst case times O(log^4 n) per edge insertion, O(log^5 n) per edge deletion, and O(log n / log log n) per query. The answer to each query is correct if the answer is .yes. and is correct with high probability if the answer is .no.. The data structure is based on a simple novel idea which can be used to quickly identify an edge in a cutset.