02-06-2012, 04:31 PM
Dynamic Graph Algorithms
Dynamic-Graph-Algorithms.pdf (Size: 362.77 KB / Downloads: 41)
INTRODUCTION
In many applications of graph algorithms, including communication
networks, VLSI design, graphics, and assembly planning, graphs are
subject to discrete changes, such as additions or deletions of edges or
vertices. In the last two 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. A dynamic graph is
a graph that is undergoing a sequence of updates. 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.
DYNAMIC PROBLEMS ON UNDIRECTED GRAPHS
This part considers fully dynamic algorithms for undirected graphs.
These algorithms maintain efficiently some property of a graph that is
undergoing structural changes defined by insertion and deletion of edges,
and/or updates of edge costs. To check the graph property throughout a
sequence of these updates, the algorithms must be prepared to answer
queries on the graph property efficiently.
General Techniques for Undirected Graphs
Many of the algorithms proposed in the literature use the same general
techniques, and hence we begin by describing these techniques. As a common
theme, most of these techniques use some sort of graph decomposition, and
partition either the vertices or the edges of the graph to be maintained.
Moreover, data structures that maintain properties of dynamically changing trees
are often used as building blocks by many dynamic graph algorithms. The basic
update operations are edge insertions and edge deletions.
Topology Trees
Topology trees have been introduced by Frederickson to maintain
dynamic trees upon insertions and deletions of edges. Given a tree T of the
forest, a cluster is a connected sub-graph of T. The cardinality of a cluster is
the number of its vertices. The external degree of a cluster is the number of
tree edges incident to it.