Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Maintaining a set of smallest subsets

Here are the operations that I'd like to perform on a hypothetical collection data structure that holds sets as its elements:

  1. Insert a set into the data structure, but: (1) if the new set is a superset of any of the existing sets, don't add it (2) if the new set is a subset of any existing sets, remove them.
  2. Enumerate all the sets currently in the collection

All the sets in question are subsets of a known finite set, say {0..10^4}.

Is there a way to do this efficiently?

like image 378
Jules Avatar asked Nov 04 '22 07:11

Jules


1 Answers

Here is a recent paper on this problem: http://research.google.com/pubs/pub36974.html

Briefly, you cannot do much better than quadratic time in the worst case; but there are some tricks to speed it up in practice.

like image 191
Falk Hüffner Avatar answered Nov 07 '22 21:11

Falk Hüffner