Coupon collecting and transversals of hypergraphs - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue Discrete Mathematics and Theoretical Computer Science Année : 2013

Coupon collecting and transversals of hypergraphs

Résumé

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.

Domaines

Mathématique discrète [cs.DM]
Fichier principal
Vignette du fichier
2331-8318-2-PB.pdf (333.77 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Service Ist Inria Sophia Antipolis-Méditerranée / I3s  : Connectez-vous pour contacter le contributeur

https://inria.hal.science/hal-00980772

Soumis le : vendredi 18 avril 2014-16:44:00

Dernière modification le : mardi 7 février 2023-03:42:44

Archivage à long terme le : lundi 10 avril 2017-15:35:24

Télécharger pour visualiser

Dates et versions

hal-00980772 , version 1 (18-04-2014)

Identifiants

Citer

Marcel Wild, Svante Janson, Stephan Wagner, Dirk Laurie. Coupon collecting and transversals of hypergraphs. Discrete Mathematics and Theoretical Computer Science, 2013, Vol. 15 no. 2 (2), pp.259--270. ⟨10.46298/dmtcs.608⟩. ⟨hal-00980772⟩

Exporter

BibTeX XML-TEI Dublin Core DC Terms EndNote DataCite

Collections

TDS-MACS
130 Consultations
1092 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More