Stationary distribution and cover time of random walks on random digraphs

DOI10.1016/j.jctb.2011.11.001zbMath1239.05167arXiv1103.4317OpenAlexW2158978530WikidataQ57401445 ScholiaQ57401445MaRDI QIDQ412164

Colin Cooper, Alan M. Frieze

Publication date: 4 May 2012

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1103.4317

zbMATH Keywords

random walkcover timerandom digraphs

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Directed graphs (digraphs), tournaments (05C20) Random walks on graphs (05C81)

Related Items (12)

On the Cover Time of the Emerging Giant ⋮ Random walk on sparse random digraphs ⋮ Discrepancy inequalities for directed graphs ⋮ A probabilistic proof of Cooper and Frieze's "First Visit Time Lemma" ⋮ Rankings in directed configuration models with heavy tailed in-degrees ⋮ Stationary distribution and cover time of sparse directed configuration models ⋮ Component structure of the vacant set induced by a random walk on a random graph ⋮ Spectrum of Markov Generators on Sparse Random Graphs ⋮ The largest strongly connected component in the cyclical pedigree model of Wakeley et al. ⋮ On the Cover Time of Dense Graphs ⋮ Diameter and stationary distribution of random \(r\)-out digraphs ⋮ Cover time of a random graph with a degree sequence II: Allowing vertices of degree two

Cites Work

• Unnamed Item
• The cover time of the preferential attachment graph
• The cover time of random geometric graphs
• The cover time of sparse random graphs
• The cover time of the giant component of a random graph
• Corrigendum: The cover time of the giant component of a random graph, Random Structures and Algorithms 32 (2008), 401-439
• An algorithm for finding hamilton cycles in random directed graphs
• A tight upper bound on the cover time for random walks on graphs
• A tight lower bound on the cover time for random walks on graphs
• The Cover Time of Random Regular Graphs
• Concentration of multivariate polynomials and its applications

This page was built for publication: Stationary distribution and cover time of random walks on random digraphs