Optimal Cover Time for a Graph-Based Coupon Collector Process
Dimitrov, Nedialko B.
Plaxton, C. Greg
MetadataShow full item record
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...
Journal of Discrete Algorithms, February, 2013The article of record as published may be located at http://dx.doi.org/10.1016/j.jda.2013.02.003