No label defined (Q3824320)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 4099308
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 4099308 |
Statements
1988
0 references
generating algorithms
0 references
k-combinations
0 references
acyclic families
0 references
0.765012264251709
0 references
0.7518451809883118
0 references
0.7423814535140991
0 references
[For the entire collection see Zbl 0655.00009.] Let U denote a set of n distinct elements and let \(S_ 1,S_ 2,...,S_ m\) be subsets of U. To list all k-combinations C of U, such that \(C\subseteq S_ i\), for some \(1\leq \ell \leq m\), an optimal running time algorithm would require \(O(\ell +kt)\) steps, where 1 is the input size and t is the number of k-combinations. In this paper, we present an algorithm for generating such k-combinations. Its running time is bounded by \(O(1+kt+mt)\), which is optimal for families of sets \({\mathcal S}\) where \(m=O(k)\). We also present two algorithms that are optimal for the so called acyclic families of sets and for the families of sets whose thickness is bounded by 2, (i.e., such that for all \(x_ i\in U\), \(x_ i\) is in at most 2 of the \(S_ i's)\).
0 references