Combinatorial Algorithms
Combinatorial Algorithms
复制标题
组合算法
DOI：
10.1007/978-3-319-29516-9_1
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Abdullah M
中科院分区：
文献类型：
--
作者：
Abdullah M
分析了给定度序列的随机图上随机游动的覆盖时间。使用仅使用局部度知识的特定类型的方案将权重分配给图的边。这会使行走的过渡偏向较低阶数的顶点。我们证明了，在大概率情况下，覆盖时间最长，而覆盖时间最小。这与[1]中给出的简单(即无偏)随机游走在同一图模型上的精确覆盖时间(具有高概率)形成了对比。这里是平均度，由于比率可以是任意大的，也可以是n的无穷大，我们可以看到该方案可以给稀疏图带来无界的速度。
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, wheredis 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. Hereis the average degree and since the ratiocan be arbitrarily large, or go to infinity withn, we see that the scheme can give an unbounded speed up for sparse graphs.