Optimal Cover Time for a Graph-Based Coupon Collector Process

dc.contributor.author	Dimitrov, Nedialko B.
dc.contributor.author	Plaxton, C. Greg
dc.date.accessioned	2013-12-05T20:56:09Z
dc.date.available	2013-12-05T20:56:09Z
dc.date.issued	2013
dc.identifier.citation	Nedialko B. Dimitrov and C. Greg Plaxton. Optimal Cover Time for a Graph-Based Coupon Collector Process. Journal of Discrete Algorithms, February, 2013, doi:10.1016/j.jda.2013.02.003
dc.identifier.uri	http://hdl.handle.net/10945/37915
dc.description	Journal of Discrete Algorithms, February, 2013	en_US
dc.description	The article of record as published may be located at http://dx.doi.org/10.1016/j.jda.2013.02.003	en_US
dc.description.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...	en_US
dc.rights	This 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.	en_US
dc.title	Optimal Cover Time for a Graph-Based Coupon Collector Process	en_US
dc.type	Article	en_US
dc.subject.author	Coupon Collector Process	en_US
dc.subject.author	Graph Covering	en_US
dc.subject.author	Sequence Argument	en_US