Algorithm question: minimal sets?

Jonathan Epstein Jonathan_Epstein at nih.gov
Tue Sep 18 11:04:13 EST 2001


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
>





More information about the Bio-soft mailing list