On the cover time and mixing time of random geometric graphs

DOI10.1016/J.TCS.2007.02.065MaRDI QIDQ2373731zbMATH OpenOpenAlexFDO

Authors Chen Avin, Gunes Ercal

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

cover timemixing timerandom graphsrandom walks

Mathematics Subject Classification ID

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

Recommendations

• Automata, Languages and Programming
• The cover time of random geometric graphs
• The cover time of random geometric graphs
• The Cover Time of Random Regular Graphs
• The cover time of two classes of random graphs
• On the Cover Time for Random Walks on Random Graphs
• On the cover time of random walks on graphs
• Cover time and mixing time of random walks on dynamic graphs
• The Cover Time of Random Digraphs
• The cover time of the giant component of a random graph

Cites work

• A tight lower bound on the cover time for random walks on graphs
• Approximate counting, uniform generation and rapidly mixing Markov chains
• Automata, Languages and Programming
• Bounds on the cover time
• Convergence Rates for Markov Chains
• Covering problems for Brownian motion on spheres
• scientific article; zbMATH DE number 3904630 (Why is no real title available?)
• scientific article; zbMATH DE number 3934150 (Why is no real title available?)
• scientific article; zbMATH DE number 1254188 (Why is no real title available?)
• scientific article; zbMATH DE number 2079333 (Why is no real title available?)
• scientific article; zbMATH DE number 819814 (Why is no real title available?)
• scientific article; zbMATH DE number 878897 (Why is no real title available?)
• Improved Bounds for Mixing Rates of Markov Chains and Multicommodity Flow
• Lower bounds for covering times for reversible Markov chains and random walks on graphs
• Multiple cover time
• On the Cover Time for Random Walks on Random Graphs
• On the cover time of planar graphs
• Random Geometric Graphs
• Sharp thresholds for monotone properties in random geometric graphs
• The bin-covering technique for thresholding random geometric graph properties
• The electrical resistance of a graph captures its commute and cover times
• The fundamental theorem of electrical networks
• The longest edge of the random minimal spanning tree
• The spectrum of a random geometric graph is concentrated

Cited in

(15)

• Distributed optimization with information-constrained population dynamics
• Localization in random geometric graphs with too many edges
• The cover time of random geometric graphs
• Cops and robbers on geometric graphs
• Diameter and broadcast time of random geometric graphs in arbitrary dimensions
• On the mixing time of geographical threshold graphs
• Linear time average consensus and distributed optimization on fixed graphs
• 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
• Resistance distance distribution in large sparse random graphs
• Theoretical Aspects of Graph Models for MANETs
• Automata, Languages and Programming
• Cover and hitting times of hyperbolic random graphs
• Thresholding random geometric graph properties motivated by ad hoc sensor networks

This page was built for publication: On the cover time and mixing time of random geometric graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2373731)