DYNAMIC GRAPH ALGORITHMS
seminar surveyer Active In SP Posts: 3,541 Joined: Sep 2010 
12012011, 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 l1 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 ,..PleaseASK HERE
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 pagePossibly Related Threads...  
Thread  Author  Replies  Views  Last Post  
DYNAMIC IMAGE RESIZING AND RESAMPLING MODULE REPORT  project girl  0  599 
15012013, 04:24 PM Last Post: project girl 

Dynamic Resource Allocation  seminar flower  0  626 
23072012, 10:55 AM Last Post: seminar flower 

TISSUESPECIFIC COMPARTMENTAL ANALYSIS FOR DYNAMIC CONTRASTENHANCED MR IMAGING OF CO  seminar paper  0  326 
12042012, 01:05 PM Last Post: seminar paper 

LOSSLESS DATA COMPRESSION ALGORITHMS  seminar class  1  2,733 
01032012, 11:42 AM Last Post: seminar paper 

Performance Analysis of Dynamic Source Routing Protocol for Ad Hoc Networks  project topics  4  3,624 
21112011, 10:13 AM Last Post: seminar addict 

SEARCHING ALGORITHMS  seminar class  0  923 
25042011, 02:23 PM Last Post: seminar class 

Dynamic Virtual Private Network  computer science crazy  0  882 
03092009, 05:40 PM Last Post: computer science crazy 

Graph Separators  computer science crazy  0  1,148 
23092008, 12:48 AM Last Post: computer science crazy 