DYNAMIC GRAPH ALGORITHMS
• 0 Vote(s) - 0 Average
• 1
• 2
• 3
• 4
• 5
 seminar surveyer Active In SP Posts: 3,541 Joined: Sep 2010 12-01-2011, 11:54 AM   Presentation1.ppt (Size: 306.5 KB / Downloads: 76) BY RAMESH.V.P -EPAHEIT039 GUIDED BY Mrs.Jayasree.P Lecturer in IT OVERVIEW 1.Introduction 2.Dynamic problems on undirected graphs 2.1 General techniques and data structures 2.2 Connectivity 3.Highly Dynamic Network problem 4.Conclusion 5.References INTRODUCTION Dynamic graph algorithms describe a whole body of algorithms and datastructures for dynamically changing graphs. 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 Dynamic graph problems are of two types 1)Fully dynamic:unlimited number of insertions and deletions of edges are allowed. 2)Partially dynamic:either insertion or deletion is allowed -Incremental:only insertions are allowed -Decremental:only deletions are allowed DYNAMIC PROBLEMS ON UNDIRECTED GRAPHS Algorithms maintain some property of an undirected graph under going a sequence of updates. Fully dynamic minimum spanning tree problem consists of maintaining a minimum spanning tree during updation. Fully dynamic connectivity algorithm must be able to update and answer -whether the graph is connected? TECHNIQUES AND DATA STRUCTURES Many of algorithms use techniques like Clustering Randomization Data structures that maintain the properties of dynamically changing trees: Topology Trees ET Trees TOPOLOGY TREES Hierarchicalrepresentation of a tree T : each level partitions the vertices of T into clusters. Clusters at level 0 contain one vertex each. -Clusters at level l>=1 form a partition of the vertices of the tree T' obtained by shrinking each cluster at level l-1 into a single vertex. Let T is a tree with maximum vertex degree 3. A restricted partition of T partitions its vertx set V in to clusters such that: (1)Each cluster of external degree 3 is of cardinality 1. (2)Each cluster of external degree less than 3 is of cardinality atmost 2. (3)No two adjacent clusters can be combined and still satisfy the above. CLUSTERING Introduced by Frederickson Clustering -partitioning graph in to connected subgraphs called clusters -each update involves only a small no:of such clusters. Decomposition by clusters applied recursively and information about subgraphs is combined with Topology trees

## Important Note..!

If you are not satisfied with above reply ,..Please

So that we will collect data for you and will made reply to the request....OR try below "QUICK REPLY" box to add a reply to this page
 Tagged Pages: seminar topiocs for graphs and trees, dynamic graph algorithms data structures, dynamic graph algorithem, clustering in dynamic graph algorithms, seminar on graph in ds, dynamic graph algorithm, a randomized algorithm for spectral clustering ppt,
 Popular Searches: pqrs graph in ecg, engineering graph paper, dynamic graph algorithms for seminar, seminar on graph in ds, topology tree in dynamic graph aogorithms, graph clustering software, dynamic graph algorithm,