The simple random walk and max-degree walk on a directed graph

DOI10.1002/rsa.20227zbMath1225.05222arXivmath/0609303MaRDI QIDQ3633018

Ravi Montenegro

Publication date: 16 June 2009

Published in: Random Structures and Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

eigenvalues; Markov chain; spectral gap; Eulerian graph; evolving sets

Mathematics Subject Classification ID

05C80: Random graphs (graph-theoretic aspects)

60J10: Markov chains (discrete-time Markov processes on discrete state spaces)

05C38: Paths and cycles

05C20: Directed graphs (digraphs), tournaments

05C81: Random walks on graphs

Cites Work

• Sharp edge, vertex, and mixed Cheeger inequalities for finite Markov kernels
• Blocking Conductance and Mixing in Random Walks