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