Name
Abstract | ||
|---|---|---|
We consider the following marking process (rw-rand) made by a random walk on an undirected graph G. Upon arrival at a vertex v, it marks v if unmarked and otherwise it marks a randomly chosen unmarked neighbor of v. We also consider a variant of this process called rw-r-rank. Here each vertex is assigned a global random rank first and then in each step, the walk marks the lowest ranked unmarked neighbor of the currently visited vertex. Depending on the degree and the expansion of the graph, we prove several upper bounds on the time required by these processes to mark all vertices. For instance, if G is a hypercube or random graph, our processes mark all vertices in time O(n), significantly speeding up the Θ(n log n)-cover time of standard random walks. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.5555/1873601.1873716 | SODA |
Keywords | Field | DocType |
random graph,random walk,undirected graph,time o,n log n,standard random walk,neighborhood exploration,upper bound,vertex v,unmarked neighbor | Random regular graph,Discrete mathematics,Combinatorics,Random graph,Loop (graph theory),Vertex (graph theory),Cycle graph,Neighbourhood (graph theory),Degree (graph theory),Random geometric graph,Mathematics | Conference |
Volume | ISBN | Citations |
135 | 978-0-89871-698-6 | 10 |
PageRank | References | Authors |
0.75 | 10 | 5 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Petra Berenbrink | 1 | 472 | 46.41 |
| Colin Cooper | 2 | 287 | 30.73 |
| Robert Elsässer | 3 | 10 | 0.75 |
| Tomasz Radzik | 4 | 1098 | 95.68 |
| Thomas Sauerwald | 5 | 575 | 39.99 |