Optimal Cover Time for a Graph-Based Coupon Collector Process
Abstract
In this paper we study the following covering process defined over an arbitrary directed graph. Each node is
initially uncovered and is assigned a random integer rank drawn from a suitable range. The process then proceeds in
rounds. In each round, a uniformly random node is selected and its lowest-ranked uncovered outgoing neighbor, if
such exists, is covered...
Description
Journal of Discrete Algorithms, February, 2013
The article of record as published may be located at http://dx.doi.org/10.1016/j.jda.2013.02.003