Minimal Covering Set: System of Distinct Representatives

  • Context: Graduate 
  • Thread starter Thread starter WWGD
  • Start date Start date
  • Tags Tags
    Set
Join the discussion
Registration is free. Ask a follow-up in this thread, or start your own.
1 reply · 2K views
Messages
7,831
Reaction score
13,158
Hi All,
Let ##s: \{s_1,s_2,...,s_j \}## be a collection of elements contained in the sets ##S:=\{S_1,S_2,...S_k \}## , no relation between ##j,k##; a given ##s_i## may be contained in one or more ##S_n##. I want to find a minimal "cover" for ##s##, i.e., the smallest subcollection of sets in ##S## that contains every element in ##s##. I think this is called an SDR : System of Distinct Representatives.
Is there a general formula dealing with this? Obviously, ##k## is an upper bound.
 
Physics news on Phys.org