A Tractable Variant of Cover Time
Georgakopoulos, Agelos
Original · EN
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.
English translation
This paper has no Arabic translation yet. Be the first: it takes a few seconds, and the result is stored for every future reader.