Speeding up cover time of sparse graphs using local knowledge
International Workshop on Combinatorial Algorithms, 2015•Springer
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)) d-1 d-2 8n\log n, where d is the minimum degree. This is in contrast to the precise cover
time of (1+ o (1)) d-1 d-2 θ dn\log n (with high probability) given in 1 for a simple (ie …
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)) d-1 d-2 8n\log n, where d is the minimum degree. This is in contrast to the precise cover
time of (1+ o (1)) d-1 d-2 θ dn\log n (with high probability) given in 1 for a simple (ie …
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 , where d is the minimum degree. This is in contrast to the precise cover time of (with high probability) given in [1] for a simple (i.e., unbiased) random walk on the same graph model. Here is the average degree and since the ratio can be arbitrarily large, or go to infinity with n, we see that the scheme can give an unbounded speed up for sparse graphs.
Springer
顯示最佳搜尋結果。 查看所有結果