Anzeige
Erschienen in:
2008 | OriginalPaper | Buchkapitel
How to Explore a Fast-Changing World (Cover Time of a Simple Random Walk on Evolving Graphs)
verfasst von : Chen Avin, Michal Koucký, Zvi Lotker
Erschienen in: Automata, Languages and Programming
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Motivated by real world networks and use of algorithms based on random walks on these networks we study the simple random walks on
dynamic
undirected graphs with fixed underlying vertex set, i.e., graphs which are modified by inserting or deleting edges at every step of the walk. We are interested in the expected time needed to visit all the vertices of such a dynamic graph, the
cover time
, under the assumption that the graph is being modified by an oblivious adversary. It is well known that on connected
static
undirected graphs the cover time is polynomial in the size of the graph. On the contrary and somewhat counter-intuitively, we show that there are adversary strategies which force the expected cover time of a simple random walk on connected dynamic graphs to be exponential. We relate this result to the cover time of static directed graphs. In addition we provide a simple strategy, the
lazy
random walk, that guarantees polynomial cover time regardless of the changes made by the adversary.