DYNAMIC GRAPH ALGORITHMS
Thread Rating:
  • 0 Vote(s) - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
seminar surveyer
Active In SP
**

Posts: 3,541
Joined: Sep 2010
#1
12-01-2011, 11:54 AM





.ppt   Presentation1.ppt (Size: 306.5 KB / Downloads: 78)

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




Reply

Important Note..!

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

ASK 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 page

Quick Reply
Message
Type your reply to this message here.


Image Verification
Please enter the text contained within the image into the text box below it. This process is used to prevent automated spam bots.
Image Verification
(case insensitive)

Possibly Related Threads...
Thread Author Replies Views Last Post
  DYNAMIC IMAGE RESIZING AND RESAMPLING MODULE REPORT project girl 0 610 15-01-2013, 04:24 PM
Last Post: project girl
  Dynamic Resource Allocation seminar flower 0 633 23-07-2012, 10:55 AM
Last Post: seminar flower
  TISSUE-SPECIFIC COMPARTMENTAL ANALYSIS FOR DYNAMIC CONTRAST-ENHANCED MR IMAGING OF CO seminar paper 0 326 12-04-2012, 01:05 PM
Last Post: seminar paper
  LOSSLESS DATA COMPRESSION ALGORITHMS seminar class 1 2,744 01-03-2012, 11:42 AM
Last Post: seminar paper
  Performance Analysis of Dynamic Source Routing Protocol for Ad Hoc Networks project topics 4 3,624 21-11-2011, 10:13 AM
Last Post: seminar addict
  SEARCHING ALGORITHMS seminar class 0 929 25-04-2011, 02:23 PM
Last Post: seminar class
  Dynamic Virtual Private Network computer science crazy 0 895 03-09-2009, 05:40 PM
Last Post: computer science crazy
  Graph Separators computer science crazy 0 1,159 23-09-2008, 12:48 AM
Last Post: computer science crazy