English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools annual

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

For a simple (unbiased) random walk on a connected graph with $n$ vertices, the cover time (the expected number of steps it takes to visit all vertices) is at most $O(n^3)$. We consider locally biased random walks, in which the probability of traversing an edge depends on the degrees of its endpoints. We confirm a conjecture of Abdullah, Cooper and Draief [2015] that the min-degree local bias rule ensures a cover time of $O(n^2)$. For this we formulate and prove the following lemma about spanning trees. Let $R(e)$ denote for edge $e$ the minimum degree among its two endpoints. We say that a weight function $W$ for the edges is feasible if it is nonnegative, dominated by $R$ (for every edge $W(e) \le R(e)$) and the sum over all edges of the ratios $W(e)/R(e)$ equals $n-1$. For example, in trees $W(e) = R(e)$, and in regular graphs the sum of edge weights is $d(n-1)$. {\bf Lemma:} for every feasible $W$, the minimum weight spanning tree has total weight $O(n)$. For regular graphs, a similar lemma was proved by Kahn, Linial, Nisan and Saks [1989].

Random Walks with the Minimum Degree Local Rule Have $O(n^2)$ Cover Time