Dynamic graph connectivity in polylogarithmic worst case time – University of Copenhagen

Dynamic graph connectivity in polylogarithmic worst case time

Talk by Valerie King, Monday May 19 at 15:15-17:00


The dynamic graph connectivity problem is the following: given a graph on a fixed set of n nodes, design a data structure to process an online sequence of updates in the form of edge insertions and deletions, and 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 for some updates. In fact, no previously known solution has worst case time per operation which is o(n1/2).

In this talk I'll explain a solution with worst case time O(log4 n) per edge insertion, O(log5 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.

This work is joint with Bruce Kapron and Ben Mountjoy.

About Valerie King

Valerie King

Valerie King, Professor, University of Victoria

Valerie King is a Professor of Computer Science at the University of Victoria.  She received an AB degree from Princeton University in Mathematics, a PhD in Computer Science under the supervision of Richard Karp and a JD, both from the University of California at Berkeley. She held post-doctoral fellowships at the University of Toronto and Princeton University and served as a research scientist at NECI, Compaq SRC and HP Labs, a Visiting Researcher/member at Microsoft SVC, Simons Institute in Berkeley, and Institute of Advanced Study in Princeton. She was a visiting associate professor at the University of Copenhagen and Hebrew University, and is currently a visiting professor at ENS in Paris.

Dr. King's current research concerns randomized algorithms and data structures and fault tolerant distributed computing.