A Tractable Variant of Cover Time

2012/06/28 by Agelos Georgakopoulos, Georgakopoulos, Agelos
Computer Science · Mathematics · #05C81 #Advanced Graph Theory Research #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Markov Chains and Monte Carlo Methods #cs.DM #math.CO #msc:05C81

paper · pdf · doi:10.48550/arxiv.1206.6605

arxiv created 2012/06/28 · openalex publication_date 2012/06/28 · arxiv updated 2012/06/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We introduce a variant of the cover time of a graph, called cover cost, in which the cost of a step is proportional to the number of yet uncovered vertices. It turns out that cover cost is more tractable than cover time; we provide an O(n⁴) algorithm for its computation, as well as some explicit formulae. The two values are not very far from each other, and so cover cost might be a useful tool in the study of cover time.

Citations

• Cover times, blanket times, and majorizing measures

Related

• The cover time, the blanket time, and the Matthews bound
• Cover times, blanket times, and majorizing measures
• Further results on the expected hitting time, the cover cost and the related invariants of graphs
• The evolution of the cover time
• Cover time of a random graph with a degree sequence II: Allowing vertices of degree two