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
RightsThis publication is a work of the U.S. Government as defined in Title 17, United States Code, Section 101. Copyright protection is not available for this work in the United States.