A coterie is a family of subsets such that every pair of subsets has at least one element in common but neither is a subset of the other.
A coterie $C$ is said to be non-dominated (ND) if there is no other coterie $D$ such that, for $\forall Q \in C$, there exists $Q' \in D$ satisfying $Q' \subseteq Q$.
We introduce an operator $\sigma$, which transforms a ND 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 $\sigma$ operations to $C$ at most $|C|+|D|-2$ times.
As another application of the $\sigma$ operation, we present an incrementally-polynomial-time algorithm for generating all regular ND coteries. We then introduce the concept of ``g-regular" function, as a generalization of availability. We show how to construct an optimum coterie $C$ with respect to a g-regular function in $O(n^3|C|)$ time. We also discuss the structures of optimum coteries with respect to a g-regular function.
DIMACS Home Page