jeudi 26 février 2015

Algorithm to find minimal set


I have a set of sets S and I want to find a minimal set of elements M such that each set in S shares at least one element with M.



S = set of sets
∀ f∈S ∃e · e∈f ∧ e∈M


For example:



S = {{1}, {1, 2, 3}, {4, 3}, {1, 5}}
M = {1, 3, 5}


Is there a name for this problem? What algorithms exist to find an approximation of M?





Aucun commentaire:

Enregistrer un commentaire