| LEP: Dynamic Graph Algorithms |
- A Software Package of Dynamic Graph Algorithms
|
|
|
-
If you want to get update information concerning this package please contact
italiano@dsi.unive.it
to be put on a mailing list.
|
|
Giuseppe F. Italiano
Dipartimento di Matematica Applicata ed Informatica Università "Ca' Foscari" di Venezia via Torino 155 30173 Mestre Italy email: italiano@dsi.unive.it |
-
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.
|
|
back to the LEDA EP index page