• Calendar

February 1, Tuesday
12:00 – 14:00

We obtain a new fully dynamic algorithm for the reachability problem in directed graphs. Our algorithm has an amortized update time of $O(m+n\log n)$ and a worst-case query time of $O(n)$, where $m$ is the (current) number of edges in the graph, and $n$ is the number of vertices in the graph. Each update operation either inserts a set of edges that touch the same vertex, or deletes an arbitrary set of edges. The algorithm is deterministic and uses fairly simple data structures. This is the first algorithm that breaks the $O(n^2)$ update barrier for all graphs with $o(n^2)$ edges.

One of the ingredients used by this new algorithm may be interesting in its own right. It is a new dynamic algorithm for strong connectivity in directed graphs with an interesting persistency property. Each insert operation creates a new version of the graph. A delete operation deletes edges from all versions. Strong connectivity queries can be made on each version of the graph. The algorithm handles each update in $O(m\alpha(m,n))$ amortized time, and each query in $O(1)$ time. Note that the update time of $O(m\alpha(m,n))$, in case of a delete operation, is the time needed for updating all versions of the graph.

This is a joint work with Uri Zwick

Bio:
Liam Roditty is a PhD student under the supervision of Prof. Uri Zwick in Tel-Aviv university. His research is focused on graph algorithms.