Dynamic Graph Algorithms

Lecturer: Giuseppe F. Italiano (University of Rome "Tor Vergata").

About the lecturer | Course Summary | Slides: 1 2 3 4 | Assignment

About the lecturer: Giuseppe F. Italiano is Professor of Computer Science at the University of Rome "Tor Vergata". His research interests are in the design, analysis, implementation and experimental evaluation of algorithms and data structures for solving theoretical and applied problems in graphs and massive data sets. He is a Fellow of the EATCS (European Association for Theoretical Computer Science).

Giuseppe F. Italiano received a PhD in Computer Science in 1991 from Columbia University. He was a Research Staff Member at the IBM T.J. Watson Research Center in Yorktown Heights, and then full professor at University of Salerno, University of Venice "Ca' Foscari" and University of Rome "Tor Vergata". In his university he was Department Chair from 2004 to 2012, Chair of the Evaluation Committee from 2002 to 2008, and is currently Vice-Rector for Quality, Evaluation and Performance.

His papers appeared at leading computer science conferences (FOCS, STOC, SODA, ICALP), and journals (Journal of the ACM, SIAM Journal on Computing, ACM Transactions on Algorithms, Theoretical Computer Science). He also served as PC chair and PC member of several leading international conferences, including FOCS, STOC, SODA, ICALP. He has been serving as Editor-in-Chief and Associate Editor in several journals in theoretical computer science, including the ACM Journal on Experimental Algorithmics, Algorithmica and Theoretical Computer Science. His research has been funded in part by several EU projects, industrial contracts and by the Italian Ministry of Education, University and Research.

Course summary: 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 tutorial 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.

Slides:


Assignment: In this set of slides you can find two clearly marked exercises. Please send the solutions to Bartek Klin (klin@you-know-what) by Monday, June 6.