Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!think.com!zaphod.mps.ohio-state.edu!wuarchive!uunet!mcsun!ub4b!kulcs!icarus.cs.kuleuven.ac.be
From: bimandre@icarus.cs.kuleuven.ac.be (Andre Marien)
Newsgroups: comp.theory
Subject: Re: Generating subsets which are not supersets
Message-ID: <3545@n-kulcs.cs.kuleuven.ac.be>
Date: 23 May 91 08:59:15 GMT
References: <1991May18.120016.1@csc.anu.edu.au>
Sender: news@cs.kuleuven.ac.be
Organization: Dept. of Computer Science (K.U.Leuven)
Lines: 24
Originator: bimandre@icarus

In article <1991May18.120016.1@csc.anu.edu.au> bdm659@csc.anu.edu.au writes:
>Let S = {1,2,...,n}, and suppose that X[1],...,X[k] are subsets of S.
>
>I wish to generate all the subsets of S which are not supersets of
>any X[i].  In a typical application, n will be about 20, k will be
>100-1000 and the X[i] will have size 3-5.
>
>Does anyone know how this can be done fast?  Practical performance
>is more important than theoretical nicety.    Thanks.

reformulation:

X[1] = { a1,   a2,      , am1 }
becomes:
C[1] = ~p1  v ~p1  v ... v ~p1
          1      2            m1

The problem becomes:
find all models M for C[1],...,C[k]

So, there is a lot of literature on this problem, but no always efficient algorithm.

Andre' Marien
bimandre@cs.kuleuven.ac.be