A tight upper bound on the cover time for random walks on graphs
From MaRDI portal
Publication:4322474
DOI10.1002/rsa.3240060106zbMath0811.60060MaRDI QIDQ4322474
Publication date: 19 April 1995
Published in: Random Structures & Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1002/rsa.3240060106
05C35: Extremal problems in graph theory
60G50: Sums of independent random variables; random walks
60C05: Combinatorial probability
Related Items
Lollipop and Lariat Symmetric Functions, Theory and Practice of Discrete Interacting Agents Models, A tight lower bound on the cover time for random walks on graphs, PERFORMANCE ANALYSIS AND EVALUATION OF RANDOM WALK ALGORITHMS ON WIRELESS NETWORKS, Unnamed Item, Analytical results for the distribution of cover times of random walks on random regular graphs, The cover time of a biased random walk on a random cubic graph, On the Cover Time of the Emerging Giant, Many Random Walks Are Faster Than One, On the Cover Time of Dense Graphs, Cover time of a random graph with a degree sequence II: Allowing vertices of degree two, Memory Efficient Anonymous Graph Exploration, The Weighted Coupon Collector’s Problem and Applications, New Bounds for Edge-Cover by Random Walk, Reversible random walks on dynamic graphs, Random walks on graphs with interval weights and precise marginals, Stationary distribution and cover time of random walks on random digraphs, Cover times, blanket times, and majorizing measures, Cover time of a random graph with given degree sequence, Tight bounds for the cover time of multiple random walks, The cover time of the preferential attachment graph, The hitting and cover times of Metropolis walks, Sum rules for hitting times of Markov chains, The hitting and cover times of random walks on finite graphs using local degree information, Random walks on edge transitive graphs, Collecting coupons on trees, and the cover time of random walks, The maximum relaxation time of a random walk, Continuous monitoring in the dynamic sensor field model, Chromatic posets, Guided sampling for large graphs, A spectral characterization for concentration of the cover time, Stationary distribution and cover time of sparse directed configuration models, Random walks on graphs and Monte Carlo methods, On the cover time of \(\lambda\)-biased walk on supercritical Galton-Watson trees, Cover time in edge-uniform stochastically-evolving graphs, The cover time of deterministic random walks for general transition probabilities, Does adding more agents make a difference? A case study of cover time for the rotor-router, The Evolution of the Cover Time, The cover time of random geometric graphs, The Cover Time of Cartesian Product Graphs, Random Walks with the Minimum Degree Local Rule Have $O(n^2)$ Cover Time, The Hitting Time of Multiple Random Walks, A multiple random walks based self-stabilizingk-exclusion algorithm in ad hoc networks, How to Design a Linear Cover Time Random Walk on a Finite Graph
Cites Work
