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

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

Authors: Marcel Wild 1; Svante Janson 2; Stephan Wagner 1; Dirk Laurie 1

  • 1 Department of Mathematical Sciences [Matieland, Stellenbosch Uni.]
  • 2 Department of Mathematics [Uppsala]

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.

https://doi.org/10.46298/dmtcs.608
Source: HAL:hal-00980772v1
Volume: Vol. 15 no. 2
Section: Analysis of Algorithms
Published on: September 9, 2013
Accepted on: June 9, 2015
Submitted on: November 21, 2012
Keywords: [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]

Share and export

Consultation statistics

This page has been seen 448 times.
This article's PDF has been downloaded 484 times.