Cover time in edge-uniform stochastically-evolving graphs

DOI10.3390/a11100149zbMath1461.60027arXiv1702.05412OpenAlexW3002693352WikidataQ129144358 ScholiaQ129144358MaRDI QIDQ2283819

Russell Martin, Ioannis Lamprou, Paul G. Spirakis

Publication date: 13 January 2020

Published in: Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

random walkcover timedynamic graphstemporal graphsedge-independentstochastically-evolving

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Sums of independent random variables; random walks (60G50) Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.) (60J20) Random walks on graphs (05C81)

Related Items (5)

Random Walks on Randomly Evolving Graphs ⋮ Reversible random walks on dynamic graphs ⋮ How fast can we reach a target vertex in stochastic temporal graphs? ⋮ Unnamed Item ⋮ How fast can we reach a target vertex in stochastic temporal graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Probabilistic methods for algorithmic discrete mathematics
• The electrical resistance of a graph captures its commute and cover times
• Flooding time in edge-Markovian dynamic graphs
• How to Explore a Fast-Changing World (Cover Time of a Simple Random Walk on Evolving Graphs)
• Maximum hitting time for random walks on graphs
• A tight upper bound on the cover time for random walks on graphs
• Markov Chains
• Random walk centrality for temporal networks
• Parsimonious flooding in dynamic graphs
• Communication in dynamic radio networks
• An Introduction to Temporal Graphs: An Algorithmic Perspective^*

This page was built for publication: Cover time in edge-uniform stochastically-evolving graphs