MPI-INF Logo
Campus Event Calendar

Event Entry

What and Who

Dynamic Graph Algorithms - Upper and Lower Bounds

Monika Henzinger
University of Vienna
INF Distinguished Lecture Series
AG 1, AG 2, AG 3, AG 4, AG 5, SWS, RG1, MMCI  
Public Audience
English

Date, Time and Location

Thursday, 22 January 2015
13:15
60 Minutes
E1 4
024
Saarbrücken

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

Jennifer Müller
--email hidden

Video Broadcast

Yes
passcode not visible
logged in users only

Jennifer Müller, 01/21/2015 14:41 -- Created document.