On the cover time of dense graphs

DOI10.1137/18M122039XMaRDI QIDQ5232158zbMATH OpenOpenAlexFDO

Authors Colin Cooper, Wesley Pegden, Alan Frieze

Publication date 29 August 2019

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

deterministic algorithmcover timedense graphs

Mathematics Subject Classification ID

Combinatorial probability (60C05)

Abstract: We consider arbitrary graphs $G$ with $n$ vertices and minimum degree at least $deltan$ where $delta>0$ is constant. If the conductance of $G$ is sufficiently large then we obtain an asymptotic expression for the cover time $C_G$ of $G$ as the solution to an explicit transcendental equation. Failing this, if the mixing time of a random walk on $G$ is of a lesser magnitude than the cover time, then we can obtain an asymptotic deterministic estimate via a decomposition into a bounded number of dense sub-graphs with high conductance. Failing this we give a deterministic asymptotic (2+o(1))-approximation of $C_G$.

Recommendations

• Cover time of a random graph with given degree sequence
• scientific article; zbMATH DE number 2079333
• Cover time of a random graph with given degree sequence
• Cover time and broadcast time
• The cover time of sparse random graphs

Cites work

• scientific article; zbMATH DE number 45266 (Why is no real title available?)
• A polynomial time approximation scheme for computing the supremum of Gaussian processes
• A tight lower bound on the cover time for random walks on graphs
• A tight upper bound on the cover time for random walks on graphs
• Asymptotics of cover times via Gaussian free fields: bounded-degree graphs and general trees
• Concentration inequalities for Markov chains by Marton couplings and spectral methods
• Cover times, blanket times, and majorizing measures
• Covering problems for Brownian motion on spheres
• Exponential concentration of cover times
• Markov chains and mixing times. With a chapter on ``Coupling from the past by James G. Propp and David B. Wilson.
• Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
• On the cover time of random walks on graphs
• Stationary distribution and cover time of random walks on random digraphs
• The Cover Time of Random Regular Graphs
• The cover time of random geometric graphs
• The cover time of sparse random graphs
• The cover time of the giant component of a random graph
• The cover time of the preferential attachment graph
• The cover times of random walks on random uniform hypergraphs

Cited in

(8)

• Cover time of a random graph with given degree sequence
• Dumbbell graphs with extremal (reverse) cover cost
• On the rank of a random binary matrix
• Connected Vertex Covers in Dense Graphs
• Cover time and broadcast time
• Cover time of a random graph with given degree sequence
• Approximating vertex cover on dense graphs
• The Cover Time of Cartesian Product Graphs

This page was built for publication: On the cover time of dense graphs

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