Wild, Marcel and Janson, Svante and Wagner, Stephan and Laurie, Dirk - Coupon collecting and transversals of hypergraphs

dmtcs:608 - Discrete Mathematics & Theoretical Computer Science, September 9, 2013, Vol. 15 no. 2
Coupon collecting and transversals of hypergraphs

Authors: Wild, Marcel and Janson, Svante and Wagner, Stephan and Laurie, Dirk

The classic Coupon-Collector Problem (CCP) is generalized. Only basic probability theory is used. Centerpiece rather is an algorithm that efficiently counts all k-element transversals of a set system.


Source : oai:HAL:hal-00980772v1
Volume: Vol. 15 no. 2
Section: Analysis of Algorithms
Published on: September 9, 2013
Submitted on: November 21, 2012
Keywords: [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]


Share

Browsing statistics

This page has been seen 66 times.
This article's PDF has been downloaded 109 times.