Efficient generation of all regular non-dominated coteries
Kazuhisa Makino, Tiko Kameda · 2000
A coterie is a family of subsets such that every pair of subsets in it has at least one element in common but neither is a subset of the other. We introduce an operator σ, which transforms a ND (non-dominated; see the Introduction for definition) coterie to another ND coterie. A “regular” coterie is a natural generalization of a “vote-assignable” coterie, which is used in some practical applications. We show that any regular ND coterie C can be transformed to any other regular ND coterie D by judiciously applying σ operations to C at most |C| + |D| - 2 times.