Discrete Mathematics & Theoretical Computer Science, Vol 15, No 2 (2013)

Font Size:  Small  Medium  Large

Coupon collecting and transversals of hypergraphs

Marcel Wild, Svante Janson, Stephan Wagner, Dirk Laurie

Abstract


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.

Full Text: PDF PostScript