::ABSTRACT ::
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) times.
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.

Download Full Seminar Report : Dynamic Graph Algorithm

Related Topics :
Virtualization seminar report
Inside Pagerank Seminar Report
Windows Registry Seminar Report
Quantum Cryptography seminar Report
computer forensic seminar report
EROS seminar Report

Tags:seminar, seminar report, computer science, dynamic graph algorithm, algorithm, download seminar report, download seminar, engineering, paper presentation, seminar topic, latest seminar topic