Optimal cover time for a graph-based coupon collector process

DOI10.1016/j.jda.2013.02.003zbMath1280.68143OpenAlexW1982325867MaRDI QIDQ2434930

Nedialko B. Dimitrov, C. Greg Plaxton

Publication date: 3 February 2014

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jda.2013.02.003

zbMATH Keywords

graph coveringcoupon collector processdelay sequence argument

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Combinatorics in computer science (68R05) Graph theory (including graph drawing) in computer science (68R10) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Cites Work

• How to emulate shared memory
• Problems and results in extremal combinatorics. II
• A stochastic process on the hypercube with applications to peer-to-peer networks
• Efficient Schemes for Parallel Communication
• Unnamed Item
• Unnamed Item