The cover time of deterministic random walks (Q612954)
From MaRDI portal
(Redirected from Item:Q3578310)
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: The cover time of deterministic random walks |
scientific article; zbMATH DE number 5758131
- The Cover Time of Deterministic Random Walks
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | The cover time of deterministic random walks |
scientific article; zbMATH DE number 5758131 |
|
Statements
The cover time of deterministic random walks (English)
0 references
The Cover Time of Deterministic Random Walks (English)
0 references
16 December 2010
0 references
20 July 2010
0 references
Summary: The rotor router model is a popular deterministic analogue of a random walk on a graph. Instead of moving to a random neighbor, the neighbors are served in a fixed order. We examine how quickly this ``deterministic random walk'' covers all vertices (or all edges). We present general techniques to derive upper bounds for the vertex and edge cover time and derive matching lower bounds for several important graph classes. Depending on the topology, the deterministic random walk can be asymptotically faster, slower or equally fast as the classic random walk. We also examine the short term behavior of deterministic random walks, that is, the time to visit a fixed small number of vertices or edges.
0 references
