The hitting and cover times of random walks on finite graphs using local degree information
From MaRDI portal
Publication:1001905
DOI10.1016/j.tcs.2008.10.020zbMath1408.05117MaRDI QIDQ1001905
Masafumi Yamashita, Satoshi Ikeda, Izumi Kubo
Publication date: 19 February 2009
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2008.10.020
Related Items
Deterministic Random Walks for Rapidly Mixing Chains, Hitting times for random walks on subdivision and triangulation graphs, Expected hitting times for random walks on quadrilateral graphs and their applications, Expected hitting times for random walks on the diamond hierarchical graphs involving some classical parameters, The hitting time of random walk on unicyclic graphs, Reversible random walks on dynamic graphs, Hitting times for random walks on tricyclic graphs, Comparison of multiple random walks strategies for searching networks, Derandomizing random walks in undirected graphs using locally fair exploration strategies, The hitting and cover times of Metropolis walks, Further results on the expected hitting time, the cover cost and the related invariants of graphs, The hitting times of random walks on bicyclic graphs, Dumbbell graphs with extremal (reverse) cover cost, The cover time of deterministic random walks for general transition probabilities, Expected hitting times for random walks on the \(k\)-triangle graph and their applications, Comparison of mean hitting times for a degree-biased random walk, Random Walks with the Minimum Degree Local Rule Have $O(n^2)$ Cover Time, Stochastic forms of non-negative matrices and Perron-regularity, How to Design a Linear Cover Time Random Walk on a Finite Graph
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Covering problems for Markov chains
- Collisions Among Random Walks on a Graph
- On a Result of Aleliunas et al. Concerning Random Walks on Graphs
- On the time taken by random walks on finite groups to visit every state
- Maximum hitting time for random walks on graphs
- On the Cover Time for Random Walks on Random 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
