17th Estonian Winter School in Computer Science (EWSCS)
XVII Eesti Arvutiteaduse Talvekool

Palmse, Estonia, February 26 -March 2, 2012

Giuseppe Italiano


Dip. di Informatica, Sistemi e Produzione
Università di Roma "Tor Vergata"
Italy

Dynamic graph algorithms

Abstract

In many applications of graph algorithms, including communication networks, graphics, assembly planning, and VLSI design, graphs are subject to discrete changes, such as additions or deletions of edges or vertices. In the last decades there has been a growing interest in such dynamically changing graphs, and a whole body of algorithms and data structures for dynamic graphs has been discovered. In a typical dynamic graph problem one would like to answer queries on graphs that are undergoing a sequence of updates, for instance, insertions and deletions of edges and vertices. The goal of a dynamic graph algorithm is to update efficiently the solution of a problem after dynamic changes, rather than having to recompute it from scratch each time. Given their powerful versatility, it is not surprising that dynamic algorithms and dynamic data structures are often more difficult to design and analyze than their static counterparts.

Course materials

Valid CSS! Valid XHTML 1.0 Strict Last changed March 3, 2012 21:54 EET by local organizers, ewscs12(at)cs.ioc.ee
EWSCS'12 page: http://cs.ioc.ee/ewscs/2012/