Henry, thanks for the term "atoms"
.
I'm not sure how I'd apply the disjoint-set data structure (union-find)
here, but its dual partition
refinement<http://en.wikipedia.org/wiki/Partition_refinement>looks
relevant. That is linear in the size of the universe, but needs to
be repeated for all the sets in S.
Oliver, the equivalence relation (sets containing x) = (sets containing y)
is conceptually very clean and simple, but I'm not sure what an efficient
implementation would look like....
Thanks again,
-s
On Mon, Apr 8, 2013 at 2:10 PM, Henry Baker <hbaker1 at pipeline.com> wrote:
> Hi Stavros:
>
> I think these minimal sets are called 'atoms'.
>
> I believe that there are 'fast' (< quadratic) algorithms for this problem.
>
> At 08:11 AM 4/8/2013, Stavros Macrakis wrote:
> >Given a set of sets S, what is the minimal set of disjoint sets D such
> that each of the original sets is a union of elements of D?
> >
> >For example, if S = { {a,b,c,d,e}, {a,c}, {c,f,g} }, then D = { {a}, {c},
> {f, g}, {b,d,e} }.
> >
> >What is the name of this problem?
> >
> >The obvious way to solve it is to calculate the full lattice of
> intersections and set differences, but the straightforward way of doing
> that seems computationally expensive. What are good algorithms for this
> problem?
> >
> > -s
>
>