Max-Planck-Institut für Informatik
max planck institut
informatik
mpii logo Minerva of the Max Planck Society
 

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)
What and Who
Title:Dynamic DFS Tree in Undirected Graphs: breaking the O(m) barrier
Speaker:Shahbaz Khan
coming from:Indian Institute of Technology Kanpur
Speakers Bio:
Event Type:AG1 Mittagsseminar (own work)
Visibility:D1
We use this to send out email in the morning.
Level:AG Audience
Language:English
Date, Time and Location
Date:Tuesday, 14 July 2015
Time:13:00
Duration:30 Minutes
Location:Saarbr├╝cken
Building:E1 4
Please note: New Room!
Room:024
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
Name(s):Andreas Wiese
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Note: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
Attachments, File(s):

Created by:Andreas Wiese, 06/16/2015 10:15 AMLast modified by:Uwe Brahm/MPII/DE, 11/24/2016 04:13 PM
  • Andreas Wiese, 06/24/2015 11:26 AM
  • Andreas Wiese, 06/22/2015 08:01 AM
  • Andreas Wiese, 06/18/2015 12:16 PM
  • Andreas Wiese, 06/16/2015 10:15 AM -- Created document.