How to Explore a Fast-Changing World (Cover Time of a Simple Random Walk on Evolving Graphs)

DOI10.1007/978-3-540-70575-8_11zbMath1152.68476OpenAlexW1847535063MaRDI QIDQ3521913

Chen Avin, Zvi Lotker, Michal Koucký

Publication date: 28 August 2008

Published in: Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-70575-8_11

Mathematics Subject Classification ID

Sums of independent random variables; random walks (60G50) Network design and communication in computer systems (68M10) Graph theory (including graph drawing) in computer science (68R10)

Related Items

Continuous-time independent edge-Markovian random graph process ⋮ Traveling salesman problems in temporal graphs ⋮ A random walk perspective on hide-and-seek games ⋮ Fast flooding over Manhattan ⋮ Grover search with lackadaisical quantum walks ⋮ An Introduction to Temporal Graphs: An Algorithmic Perspective ⋮ Toward a Theory of Markov Influence Systems and their Renormalization ⋮ Distributed exploration of dynamic rings ⋮ On Verifying and Maintaining Connectivity of Interval Temporal Networks ⋮ The complexity of optimal design of temporally connected graphs ⋮ Coordinated consensus in dynamic networks ⋮ Error-free multi-valued consensus with byzantine failures ⋮ Distributed graph coloring in a few rounds ⋮ MIS on trees ⋮ Toward more localized local algorithms ⋮ The complexity of robust atomic storage ⋮ Resilience of mutual exclusion algorithms to transient memory faults ⋮ The impact of memory models on software reliability in multiprocessors ⋮ A complexity separation between the cache-coherent and distributed shared memory models ⋮ From bounded to unbounded concurrency objects and back ⋮ The space complexity of long-lived and one-shot timestamp implementations ⋮ Locally checkable proofs ⋮ Fault-tolerant spanners ⋮ Adaptively secure broadcast, revisited ⋮ Scalable rational secret sharing ⋮ Analyzing consistency properties for fun and profit ⋮ Transforming worst-case optimal solutions for simultaneous tasks into all-case optimal solutions ⋮ Optimal-time adaptive strong renaming, with applications to counting ⋮ The round complexity of distributed sorting ⋮ A tight unconditional lower bound on distributed randomwalk computation ⋮ Minimum congestion mapping in a cloud ⋮ Conflict on a communication channel ⋮ Stability of a peer-to-peer communication system ⋮ Tight bounds on information dissemination in sparse mobile networks ⋮ Time-efficient randomized multiple-message broadcast in radio networks ⋮ Faster information dissemination in dynamic networks via network coding ⋮ Convergence of the quantile admission process with veto power ⋮ Efficient routing in carrier-based mobile networks ⋮ Reversible random walks on dynamic graphs ⋮ Efficient live exploration of a dynamic ring with mobile robots ⋮ Causality, influence, and computation in possibly disconnected synchronous dynamic networks ⋮ Temporal flows in temporal networks ⋮ Sharp Thresholds in Random Simple Temporal Graphs ⋮ How fast can we reach a target vertex in stochastic temporal graphs? ⋮ On a cover time problem on a dynamic graph with steps at random times ⋮ Exploration of carrier-based time-varying networks: the power of waiting ⋮ Exploration of dynamic tori by multiple agents ⋮ Order optimal information spreading using algebraic gossip ⋮ Parsimonious flooding in dynamic graphs ⋮ Information Spreading in Dynamic Networks: An Analytical Approach ⋮ Random walk centrality for temporal networks ⋮ Random walk in changing environment ⋮ Exploration of dynamic networks: tight bounds on the number of agents ⋮ Temporal network optimization subject to connectivity constraints ⋮ Fast and compact self-stabilizing verification, computation, and fault detection of an MST ⋮ Polynomial anonymous dynamic distributed computing without a unique leader ⋮ A faster exact-counting protocol for anonymous dynamic networks ⋮ Searching for black holes in subways ⋮ Information spreading in dynamic graphs ⋮ Structuring unreliable radio networks ⋮ Smoothed analysis of dynamic networks ⋮ Byzantine agreement with homonyms ⋮ Distributed deterministic edge coloring using bounded neighborhood independence ⋮ Compact policy routing ⋮ Cover time in edge-uniform stochastically-evolving graphs ⋮ The cost of global broadcast in dynamic radio networks ⋮ How fast can we reach a target vertex in stochastic temporal graphs ⋮ Out-of-equilibrium random walks ⋮ Polynomial anonymous dynamic distributed computing without a unique leader ⋮ Polynomial Counting in Anonymous Dynamic Networks with Applications to Anonymous Dynamic Algebraic Computations ⋮ An Introduction to Temporal Graphs: An Algorithmic Perspective^* ⋮ Xheal ⋮ Distributed computation in dynamic networks via random walks ⋮ Distributed community detection in dynamic graphs ⋮ On the expressivity of time-varying graphs ⋮ Distributed agreement in dynamic peer-to-peer networks