Name
Abstract | ||
|---|---|---|
We analyse the cover time of a random walk on a random graph of a given degree sequence. Weights are assigned to the edges of the graph using a certain type of scheme that uses only local degree knowledge. This biases the transitions of the walk towards lower degree vertices. We demonstrate that, with high probability, the cover time is at most ((1+o(1))frac{d-1}{d-2}8nlog n), where d is the minimum degree. This is in contrast to the precise cover time of ((1+o(1))frac{d-1}{d-2}frac{theta }{d} nlog n) (with high probability) given in [1] for a simple (i.e., unbiased) random walk on the same graph model. Here (theta ) is the average degree and since the ratio (theta /d) can be arbitrarily large, or go to infinity with n, we see that the scheme can give an unbounded speed up for sparse graphs. |
Year | Venue | Field |
|---|---|---|
2015 | IWOCA | Discrete mathematics,Binary logarithm,Graph,Combinatorics,Random graph,Vertex (geometry),Random walk,Infinity,Degree (graph theory),Arbitrarily large,Mathematics |
DocType | Citations | PageRank |
Conference | 1 | 0.41 |
References | Authors | |
3 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Mohammed Amin Abdullah | 1 | 10 | 2.68 |
| Colin Cooper | 2 | 857 | 91.88 |
| Moez Draief | 3 | 168 | 18.57 |