On the cover time of random walks on graphs
From MaRDI portal
Publication:1823548
DOI10.1007/BF01048274zbMath0681.60064OpenAlexW2084768526MaRDI QIDQ1823548
Noam Nisan, Nathan Linial, Michael E. Saks, Jeffry Kahn
Publication date: 1989
Published in: Journal of Theoretical Probability (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf01048274
every vertexexpected time needed for a randm walk on a finite graph to visitexpected time needed for a randm walk on a finite graph to visit every vertexrandom walks on arbitrary graphs
Random graphs (graph-theoretic aspects) (05C80) Sums of independent random variables; random walks (60G50)
Related Items
Universal traversal sequences with backtracking., Analytical results for the distribution of cover times of random walks on random regular graphs, Covering with blocks in the non-symmetric case, Random Walks with the Minimum Degree Local Rule Have $O(n^2)$ Cover Time, A spectrum of time-space trade-offs for undirected \(s-t\) connectivity, Length lower bounds for reflecting sequences and universal traversal sequences, Random walks on edge transitive graphs, The electrical resistance of a graph captures its commute and cover times, A tight lower bound on the cover time for random walks on graphs, Reversible random walks on dynamic graphs, Multiple random walks on graphs: mixing few to cover many, Classification by restricted random walks, Improved length lower bounds for reflecting sequences, Cover times, blanket times, and majorizing measures, Sensitivity of Mixing Times in Eulerian Digraphs, Stationary distribution and cover time of sparse directed configuration models, The distribution of first hitting times of randomwalks on Erdős–Rényi networks, On the time to traverse all edges of a graph, The distribution of first hitting times of random walks on directed Erdős–Rényi networks, Impact of memory size on graph exploration capability, Expected cover times of random walks on symmetric graphs, Exponential concentration of cover times, A model of self‐avoiding random walks for searching complex networks, A bound for the covering time of random walks on graphs, Laplace eigenvalues of graphs---a survey, Lower bounds on the length of universal traversal sequences, Multiparty protocols, pseudorandom generators for Logspace, and time- space trade-offs, Covering times of random walks on bounded degree trees and other graphs, Topology-hiding computation on all graphs, On the Cover Time of Dense Graphs, Bounds on the cover time, New Bounds for Edge-Cover by Random Walk, The distribution of first hitting times of non-backtracking random walks on Erdős–Rényi networks, Analytical results for the distribution of first hitting times of random walks on random regular graphs
Cites Work
