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

      0 references
      0 references
      1988
      0 references
      generating algorithms
      0 references
      k-combinations
      0 references
      acyclic families
      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

      Identifiers