A Tractable Variant of Cover Time
classification
🧮 math.CO
cs.DM
keywords
covercosttimetractablevariantalgorithmcalledcomputation
read the original 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^4)$ 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.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.