I just sent composed a long response to this which may have been lost due to
operator error
Here's a summary: I believe that this problem is known as the Set Cover
Decision Problem, and is NP-Hard, i.e., it requires exponential time.
Here are some resources:
http://x86.cs.duke.edu/~mlittman/courses/Archive/cps130-97/lectures/lect23/n
ode16.html
http://mscmga.ms.ic.ac.uk/jeb/jeb.html#set
HTH,
-Jonathan
"Charlie" <cckim at stanford.edu> wrote in message
news:Pine.GSO.4.31.0109131835160.232-100000 at saga12.Stanford.EDU...
>> I have an algorithmic problem that I suspect has already been solved long
> ago, but, alas, I am a biologist.
>> And so:
>> I have a large number of sets of data, which includes many members each.
> I would like to known the smallest possible union of these sets of data
> that would include every member.
>> An example:
> D1 = (A, B, C, D) (dataset 1 contains members A, B, C)
> D2 = (A, B, D)
> D3 = (C, D, E)
> D4 = (Z)
>> The smallest set of data which would include all members would be D1, D3,
> and D4.
>> Does anyone know an algorithm that does this?
>> Thanks in advance,
> Charlie
>
