max planck institut
informatik

# MPI-INF or MPI-SWS or Local Campus Event Calendar

 << Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
Title: Dynamic DFS Tree in Undirected Graphs: breaking the O(m) barrier Shahbaz Khan Indian Institute of Technology Kanpur AG1 Mittagsseminar (own work) D1We use this to send out email in the morning. AG Audience English
Date: Tuesday, 14 July 2015 13:00 30 Minutes Saarbrücken E1 4 Please note: New Room! 024
 Depth first search (DFS) tree is a fundamental data structure for solving various problems in graphs. It is well known that it takes $O(m+n)$ time to build a DFS tree for a given undirected graph $G=(V,E)$ on $n$ vertices and $m$ edges. We address the problem of maintaining a DFS tree when the graph is undergoing {\em updates} (insertion or deletion of vertices or edges). We present the following results for this problem. 1- Fault tolerant DFS tree There exists a data structure of size $O(m\log n)$ such that given any $k$ updates, a DFS tree for the resulting graph can be reported in \tilde{O}(nk) (hiding the poly-logarithmic factors.) worst case time. When the $k$ updates are deletions only, this directly implies an $\tilde{O}(nk)$ time fault tolerant algorithm for a DFS tree. 2- Fully dynamic DFS tree There exists a fully dynamic algorithm for maintaining a DFS tree that takes worst case $\tilde{O}(\sqrt{mn})$ time per update for any arbitrary online sequence of updates. Our results are the first $o(m)$ worst case time results for maintaining a DFS tree in a dynamic setting. Our fully dynamic algorithm provides, in a seamless manner, the first non-trivial algorithm with $O(1)$ query time and $o(m)$ worst case update time for the dynamic subgraph connectivity, bi-connectivity, 2 edge-connectivity. We also present the conditional lower bound of $\Omega(n)$ time per update for maintenance of a DFS tree.
Name(s): Andreas Wiese