Transformations on regular nondominated coteries and their applications

A coterie under an underlying set U is a family of subsets of U such that e very pair of subsets has at least one element in common, but neither is a s ubset of the other. A coterie C under U is said to be nondominated (ND) if there is no other coterie D under U such that, for every Q is an element of C, there exists Q' is an element of D satisfying Q' subset of or equal to Q. We introduce the operation sigma which transforms a ND coterie to another N D coterie. A regular coterie is a natural generalization of a vote-assignab le coterie. We show that any regular ND coterie C can be transformed to any other regular ND coterie D by judiciously applying the sigma operation 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 i ntroduce the concept of a g-regular functional as a generalization of avail ability. We show how to construct an optimum coterie C with respect to a g- regular functional in O(n(3)\C\) time, where n = \U\. Finally, we discuss t he structures of optimum coteries. with respect to a g-regular functional.