Efficient generation of All Regular Non-Dominated Coteries

Kazuhisa Makino and Tiko Kameda

To appear at Nineteenth Annual ACM SIGACT-SIGOPS Symposium on PRINCIPLES OF DISTRIBUTED COMPUTING (PODC 2000), Portland, Oregon, 16-19 July 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 sigma, 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 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 a ``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.