Random Walk on Directed Dynamic Graphs

O. Denysyuk and L. Rodrigues

Selected sections of this report were published in the International Workshop on Dynamic Networks: Algorithms and Security (DYNAS'10), Bordeaux, France, July, 2010.

Abstract

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(dmax n^3 log^2 n) of the cover time for balanced dynamic graphs.

Also available extended report (pdf)

Luís Rodrigues