Random Walk on Directed Dynamic Graphs

Details Random Walk on Directed Dynamic Graphs Random Walk on Directed Dynamic Graphs

2011-01-31

arxiv.org/abs/1101.5944v2

Computer Science

Data Structures and Algorithms

This paper has been withdrawn by the author

Scientific paper

Dynamic graphs have emerged as an appropriate model to capture the changing nature of many modern networks, such as peer-to-peer overlays and mobile ad hoc networks. Most of the recent research on dynamic networks has only addressed the undirected dynamic graph model. However, realistic networks such as the ones identified above are directed. In this paper we present early work in addressing the properties of directed dynamic graphs. In particular, we explore the problem of random walk in such graphs. We assume the existence of an oblivious adversary that makes arbitrary changes in every communication round. We explore the problem of covering the dynamic graph, that even in the static case can be exponential, and we establish an upper bound O(d_max n^3 log^2 n) of the cover time for balanced dynamic graphs.

Affiliated with

Also associated with

No associations

Rating

Random Walk on Directed Dynamic Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Random Walk on Directed Dynamic Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Random Walk on Directed Dynamic Graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-647857