On the cover time of dense graphs

DOI10.1137/18M122039XzbMATH Open1420.60007arXiv1810.04772OpenAlexW2965991765MaRDI QIDQ5232158FDOQ5232158

Alan Frieze, Colin Cooper, Wesley Pegden

Publication date: 29 August 2019

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

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$.

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

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

zbMATH Keywords

deterministic algorithmcover timedense graphs

Mathematics Subject Classification ID

Combinatorial probability (60C05)

Cites Work

• A tight upper bound on the cover time for random walks on graphs
• A tight lower bound on the cover time for random walks on graphs
• Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
• Title not available (Why is that?)
• Concentration inequalities for Markov chains by Marton couplings and spectral methods
• Cover times, blanket times, and majorizing measures
• The cover time of the giant component of a random graph
• Covering problems for Brownian motion on spheres
• The cover times of random walks on random uniform hypergraphs
• The Cover Time of Random Regular Graphs
• Asymptotics of cover times via Gaussian free fields: bounded-degree graphs and general trees
• Stationary distribution and cover time of random walks on random digraphs
• The cover time of random geometric graphs
• The cover time of sparse random graphs
• The cover time of the preferential attachment graph
• On the cover time of random walks on graphs
• Title not available (Why is that?)
• Exponential concentration of cover times
• A polynomial time approximation scheme for computing the supremum of Gaussian processes

Cited In (5)

• Dumbbell graphs with extremal (reverse) cover cost
• On the rank of a random binary matrix
• Connected Vertex Covers in Dense Graphs
• 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)