On the cover time and mixing time of random geometric graphs

DOI10.1016/j.tcs.2007.02.065zbMath1115.68167OpenAlexW2155869384MaRDI QIDQ2373731

Gunes Ercal, Chen Avin

Publication date: 16 July 2007

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2007.02.065

zbMATH Keywords

random walksrandom graphsmixing timecover time

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20)

Related Items

Cops and Robbers on Geometric Graphs, Resistance distance distribution in large sparse random graphs, Diameter and broadcast time of random geometric graphs in arbitrary dimensions, Localization in random geometric graphs with too many edges, On the mixing time of geographical threshold graphs, Linear Time Average Consensus and Distributed Optimization on Fixed Graphs, Theoretical Aspects of Graph Models for MANETs, The cover time of random geometric graphs, PERFORMANCE ANALYSIS AND EVALUATION OF RANDOM WALK ALGORITHMS ON WIRELESS NETWORKS, The Normalized Graph Cut and Cheeger Constant: From Discrete to Continuous, Distributed optimization with information-constrained population dynamics

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Covering problems for Brownian motion on spheres
• Approximate counting, uniform generation and rapidly mixing Markov chains
• The longest edge of the random minimal spanning tree
• The electrical resistance of a graph captures its commute and cover times
• On the cover time of planar graphs
• Bounds on the cover time
• Lower bounds for covering times for reversible Markov chains and random walks on graphs
• The spectrum of a random geometric graph is concentrated
• Multiple cover time
• Sharp thresholds For monotone properties in random geometric graphs
• On the Cover Time for Random Walks on Random Graphs
• Improved Bounds for Mixing Rates of Markov Chains and Multicommodity Flow
• Random Geometric Graphs
• A tight lower bound on the cover time for random walks on graphs
• Convergence Rates for Markov Chains
• Automata, Languages and Programming
• The fundamental theorem of electrical networks