Transformation of Regular Non-Dominated Coteries
Kazuhisa Makino, Tiko Kameda · 1999
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 8Q 2 C, there exists Q 0 2 D satisfying Q 0 Q. We introduce an operator , 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 operations to C at most jCj + jDj 2 times. As another application of the 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³|C|) time. We also discus...