Speaker: Giuseppe F. Italiano (Università di Roma “Tor Vergata”)
Title: Dynamic Graph Algorithms
Place: GSSI (Room B)
Mon 13/06/2016, 11:00-13:00
Tue 14/06/2016, 09:30-11:30
Wed 15/06/2016, 09:30-11:30
The design of dynamic graph algorithms is one of the classic areas in theoretical computer science. In this setting, the input of a graph problem is being changed via a sequence of updates, such as edge insertions and deletions. A dynamic graph algorithm aims at maintaining a given property P on a graph subject to dynamic updates. A dynamic graph algorithm should process queries on property P quickly, and perform update operations faster than recomputing from scratch, as carried out by the fastest static algorithm. We say that an algorithm is fully dynamic if it can handle both edge insertions and edge deletions. A partially dynamic algorithm can handle either edge insertions or edge deletions, but not both: we say that it is incremental if it supports insertions only, and decremental if it supports deletions only. This course will consist of two parts. The goal of the first part is to present the main algorithmic techniques used to solve dynamic problems on undirected graphs. To illustrate those techniques, we will focus particularly on dynamic minimum spanning trees and on connectivity problems. In the second part we deal with dynamic problems on directed graphs, and we investigate as paradigmatic problems the dynamic maintenance of transitive closure and shortest paths.
Interestingly enough, dynamic problems on directed graphs seem much harder to solve than their counterparts on undirected graphs, and require completely different techniques and tools.