The power of two choices for random walks

DOI10.1017/S0963548321000183MaRDI QIDQ5886308zbMATH OpenFDO

Authors John Haslegrave, Thomas Sauerwald, John Sylvester, Agelos Georgakopoulos

Publication date 31 March 2023

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

cover timeErdős-Rényi random graph

Mathematics Subject Classification ID

Structural characterization of families of graphs (05C75) Random graphs (graph-theoretic aspects) (05C80) Random walks on graphs (05C81) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• How Well Do Random Walks Parallelize?
• Many Random Walks Are Faster Than One
• On the cover time of random walks on graphs
• The hitting and cover times of random walks on finite graphs using local degree information
• A Technique for Lower Bounding the Cover Time

Cites work

• A new polynomial-time algorithm for linear programming
• Achlioptas process phase transitions are continuous
• Addendum to ‘avoiding a giant component’
• Balanced Allocations
• Balanced allocations: the heavily loaded case
• Biased random walks
• Birth control for giants
• Choice and Bias in Random Walks
• Concentration Inequalities and Martingale Inequalities: A Survey
• Cover times, blanket times, and majorizing measures
• Creating a Giant Component
• Derandomizing Random Walks in Undirected Graphs Using Locally Fair Exploration Strategies
• Deterministic walks with choice
• Explosive percolation in random networks
• Finite state Markovian decision processes
• Geometric algorithms and combinatorial optimization.
• Greedy Random Walk
• scientific article; zbMATH DE number 6125590 (Why is no real title available?)
• Markov chains and mixing times. With a chapter on ``Coupling from the past by James G. Propp and David B. Wilson.
• On the Laplacian Eigenvalues of G_n,p
• Preferential attachment with choice
• Probability on trees and networks
• Random graphs.
• Random walks which prefer unvisited edges: exploring high girth even degree expanders in linear time
• Some simplified NP-complete graph problems
• The cover time of a biased random walk on a random cubic graph
• The cover time of sparse random graphs
• The electrical resistance of a graph captures its commute and cover times
• The power of choice in random walks: An empirical study
• The power of choice over preferential attachment
• Weakly chained matrices, policy iteration, and impulse control

Cited in

(6)

• Biased random walks
• Cover time on a square lattice by two colored random walkers
• The power of choice in random walks: An empirical study
• The cover time of a (multiple) Markov chain with rational transition probabilities is rational
• Multiple random walks on graphs: mixing few to cover many
• The Power of Two Choices for Random Walks

This page was built for publication: The power of two choices for random walks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5886308)