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
Abstract
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.