The hitting and cover times of random walks on finite graphs using local degree information

DOI10.1016/j.tcs.2008.10.020zbMath1408.05117OpenAlexW1978196657MaRDI 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

zbMATH Keywords

random walkhitting timecover time

Mathematics Subject Classification ID

Vertex degrees (05C07) Random walks on graphs (05C81)

Related Items

Further results on the expected hitting time, the cover cost and the related invariants of graphs ⋮ Random Walks with the Minimum Degree Local Rule Have $O(n^2)$ Cover Time ⋮ Stochastic forms of non-negative matrices and Perron-regularity ⋮ Deterministic Random Walks for Rapidly Mixing Chains ⋮ Reversible random walks on dynamic graphs ⋮ Hitting times for random walks on tricyclic graphs ⋮ Comparison of mean hitting times for a degree-biased random walk ⋮ Comparison of multiple random walks strategies for searching networks ⋮ Derandomizing random walks in undirected graphs using locally fair exploration strategies ⋮ Hitting times for random walks on subdivision and triangulation graphs ⋮ The hitting and cover times of Metropolis walks ⋮ 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 times of random walks on bicyclic graphs ⋮ The cover time of deterministic random walks for general transition probabilities ⋮ How to Design a Linear Cover Time Random Walk on a Finite Graph ⋮ Expected hitting times for random walks on the \(k\)-triangle graph and their applications ⋮ The hitting time of random walk on unicyclic graphs ⋮ Dumbbell graphs with extremal (reverse) cover cost

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