Reversible random walks on dynamic graphs
From MaRDI portal
Publication:6063351
DOI10.1002/rsa.21164zbMath1526.05129arXiv2102.08002OpenAlexW4381510237MaRDI QIDQ6063351
Takeharu Shiraga, Nobutaka Shimizu
Publication date: 7 November 2023
Published in: Random Structures & Algorithms (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2102.08002
Random graphs (graph-theoretic aspects) (05C80) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Random walks on graphs (05C81)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Merging for inhomogeneous finite Markov chains. II: Nash and log-Sobolev inequalities
- Tight bounds for the cover time of multiple random walks
- Parsimonious flooding in dynamic graphs
- Covering problems for Markov chains
- Eigenvalue bounds on convergence to stationarity for nonreversible Markov chains, with an application to the exclusion process
- The hitting and cover times of Metropolis walks
- The hitting and cover times of random walks on finite graphs using local degree information
- Merging for time inhomogeneous finite Markov chains. I: Singular values and stability
- On the cover time of random walks on graphs
- Distributed probabilistic polling and applications to proportionate agreement
- Cover time in edge-uniform stochastically-evolving graphs
- Convergence of some time inhomogeneous Markov chains via spectral techniques
- Rumor spreading in random evolving graphs
- Speeding Up Cover Time of Sparse Graphs Using Local Knowledge
- Flooding Time of Edge-Markovian Evolving Graphs
- Random Walks with the Minimum Degree Local Rule Have $O(n^2)$ Cover Time
- How to Explore a Fast-Changing World (Cover Time of a Simple Random Walk on Evolving Graphs)
- How Well Do Random Walks Parallelize?
- Maximum hitting time for random walks on graphs
- Uniform coupling of non-homogeneous Markov chains
- Trading Space for Time in Undirected s-t Connectivity
- A tight upper bound on the cover time for random walks on graphs
- Cover time and mixing time of random walks on dynamic graphs
- The Linear Voting Model
- Bounds on the Voter Model in Dynamic Networks
- Crawling on Simple Models of Web Graphs
- Random Walks on Randomly Evolving Graphs
- Random walks on graphs: new bounds on hitting, meeting, coalescing and returning
- On coalescence time in graphs: When is coalescing as fast as meeting?: Extended Abstract
- Theory of Evolutionary Computation
- On the coalescence time of reversible random walks
- Coalescing Random Walks and Voting on Connected Graphs
This page was built for publication: Reversible random walks on dynamic graphs
