LEDA Extension Package
Dynamic Graph Algorithms

Introduction

Traditional graph algorithms operate on static graphs. A fixed graph is given, and an algorithmic problem (e.g., "Is the graph planar?") is solved on the graph. Dynamic graphs are not fixed in time, but can evolve through local changes of the graph. The algorithmic problem has to be re-solved quickly after each modification. Dynamic graphs model many graphs occurring in real-life applications much more closely, because no large system is truly static. In network routing, for instance, a communications network changes as nodes and links go down and up due to failures and repairs.

A dynamic graph algorithm is a data structure operating on a graph supporting two types of operations: updates and queries. An update is a local change of the graph (e.g., insertion or deletion of an edge) and a query is a question about a certain property of the  current graph (e.g., "Are nodes u and v connected in the current graph?"). The aim of such a data structure is to use structural information about the current graph in order to handle an update faster than by  the obvious solution, that is recomputing everything from scratch with a static algorithm. Usually, queries take less time than updates, and the sequence of operations (updates and queries) is not known in advance.

LEDA is a library of data types and algorithms for combinatorial and geometrical computing in C++. In particular, LEDA contains flexible and powerful data types and a wealth of algorithms for computational problems in graph theory. However, there is yet only few support for dynamic graph algorithms.

The aim of this project is to add common dynamic graph algorithms to LEDA and to enhance the support for implementing dynamic graph algorithms with LEDA. This is a LEDA Extension Package (LEP) which is shipped as an optional library with LEDA.

State

The second beta version of the package is available.

People

Halle
David Alberts (alberts@informatik. uni-halle.de)
Rome
Umberto Nanni (nanni@dis.uniroma1.it)
Giulio Pasqualone (pasqualo@dis.uniroma1.it)
Saarbrücken
Christos Zaroliagis (zaro@mpi-sb.mpg.de)
Salerno
Pippo Cattaneo (cattaneo@dia.unisa.it) (coordinator)
Venice
Giuseppe F. Italiano (italiano@dsi.unive.it) (coordinator)

Contributions

Halle
beta versions: Henzinger and King's algorithm, common base cla ss
Rome
beta versions: dynamic single source shortest paths in directe d graphs
planned: variants of the basic algorithm, a version for undire cted graphs
Saarbrücken
beta versions: dynamic transitive closure and reachability
planned: incremental biconnectivity
Salerno, Venice
beta versions: sparsification, Frederickson's algorithm
planned: 2-edge connectivity

Related Papers

The LEP Dynamic Graphs Group , 6 Jul 1998