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 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
Language:English
Date, Time and Location
Date:Thursday, 22 January 2015
Time:13:15
Duration:60 Minutes
Location:Saarbrücken
Building:E1 4
Please note: New Room!
Room:024
Abstract
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.
Contact
Name(s):Jennifer Müller
Video Broadcast
Video Broadcast:YesTo Location:
To Building:To Room:
Meeting ID:
Tags, Category, Keywords and additional notes
Note:
Attachments, File(s):
  • Jennifer Müller, 01/21/2015 02:41 PM -- Created document.