Counting or producing all fixed cardinality transversals

Abstract

An algorith to count, or alternatively generate, all k-element transversals of a set system is presented and compared with three known methods. For special cases it works in output-linear time.

This improves upon the previous version, and is to appear (with identical content) in Algorithmica

References in corpus (2)

• Computing the output distribution and selection probabilities of a stack filter from the DNF of its positive Boolean function
• Coupons collecting with or without replacement, and with multipurpose coupons