12-01-2011, 11:54 AM
Presentation1.ppt (Size: 306.5 KB / Downloads: 91)
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