MPI-INF Logo
Campus Event Calendar

Event Entry

What and Who

Dynamic DFS Tree in Undirected Graphs: breaking the O(m) barrier

Shahbaz Khan
Indian Institute of Technology Kanpur
AG1 Mittagsseminar (own work)
AG 1  
AG Audience
English

Date, Time and Location

Tuesday, 14 July 2015
13:00
30 Minutes
E1 4
024
Saarbrücken

Abstract

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.

Contact

Andreas Wiese
--email hidden
passcode not visible
logged in users only

Tags, Category, Keywords and additional notes

This is a joint work with Surender Baswana , Shreejit Ray Chaudhury
and Keerti Choudhary
(Indian Institute of Technology Kanpur).

Manuscript: http://arxiv.org/abs/1502.02481

Andreas Wiese, 06/24/2015 11:26
Andreas Wiese, 06/22/2015 08:01
Andreas Wiese, 06/18/2015 12:16
Andreas Wiese, 06/16/2015 10:15 -- Created document.