Max-Planck-Institut für Informatik
max planck institut
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 Graph Algorithms - Upper and Lower Bounds
Speaker:Monika Henzinger
coming from:University of Vienna
Speakers Bio:
Event Type:INF Distinguished Lecture Series
Visibility:D1, D2, D3, D4, D5, SWS, RG1, MMCI
We use this to send out email in the morning.
Level:Public Audience
Date, Time and Location
Date:Thursday, 22 January 2015
Duration:60 Minutes
Building:E1 4
Please note: New Room!
Dynamic graph algorithms are data structures that maintain properties of
graphs while they are modified by edge deletions and insertions. These
data structures can be used, for example, to efficiently detect deadlocks
in operating systems, compute shortest-paths in navigation systems,
or to speed up static algorithms, such as algorithms used in computer-aided
verification or certain multi-commodity flow algorithms, that solve multiple
graph propblems on very similar graphs.

While basic properties, such as connectivity, in undirected graphs can be
maintained in time polylogarithmic in the size of the graph per edge update,
no such bounds are known for basic properties, such as reachability, in
directed graphs or more sophisticated graph properties, such as shortest paths,
in undirected graphs. We will present the state of the art for these problems,
giving both upper and (conditional) lower bounds. Conditional lower bounds
result from a relatively new research direction, where similar to hardness
reductions in complexity theory, we show that based on the assumption that some
well-known problems, such as Boolean matrix multiplication, cannot be solved fast,
certain dynamic problems cannot be solved in polylogarithmic time per operation.
Name(s):Jennifer Müller
Video Broadcast
Video Broadcast:YesTo Location:
To Building:To Room:
Meeting ID:
Tags, Category, Keywords and additional notes
Attachments, File(s):
  • Jennifer Müller, 01/21/2015 02:41 PM -- Created document.