Dynamic Graph Algorithms

                           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. All the dynamic algorithms are able to maintain dynamically the
graph property at a cost (per update operation) which is significantly smaller than the cost of recomputing the graph property from scratch. The three different data structures that maintain properties of dynamically changing trees: topology trees, ET trees, and top trees. The update of these trees because of an edge insertion or deletion can be supported in O(logn) time.
The fully dynamic minimum spanning tree problem consists of maintaining a minimum spanning forest of a graph during insertions of edges, deletions of edges, and edge cost changes. A fully dynamic connectivity algorithm must be able to insert edges, delete edges, and answer a query on whether the graph is connected, or whether two vertices are in the same connected component. The algorithm answers connectivity queries in O(logn/ log log n) worst-case running time while supporting edge insertions and deletions in O(log n) amortized time. One application of dynamic graph algorithm is in a Highly Dynamic Network Problem(HDN problem).A reliable algorithm guarantees that a message from source reaches the destination nodes in a polynomially bounded time period, i.e, it satisfies the correctness and termination criteria.

   Download :     Full Report (.doc)