patternMinor
Count all possible unions in a collection of sets
Viewed 0 times
allcollectionpossibleunionscountsets
Problem
Say we have a collections of sets $\mathcal X = \{X_1, \dots, X_n\}$ (not necessarily disjoint), and we want to count the number of possible unions of sets in $\mathcal X$, i.e. the size of $\{\bigcup_{Y \in \mathcal Y} Y \,|\, \mathcal Y \subseteq \mathcal X \}$.
Is there a name for this problem?
What are the fastest algorithms to solve this problem?
Is there a name for this problem?
What are the fastest algorithms to solve this problem?
Solution
I found the answer here.
It is called the union closure and the complexity appears to be the same as computing the number of maximal independent sets in a bipartite graph.
It is called the union closure and the complexity appears to be the same as computing the number of maximal independent sets in a bipartite graph.
Context
StackExchange Computer Science Q#33571, answer score: 4
Revisions (0)
No revisions yet.