## DIMACS TR: 99-41

## Transformation of Regular Non-Dominated Coteries

### Authors: Kazuhisa Makino and Tiko Kameda

**
ABSTRACT
**

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.

Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1999/99-41.ps.gz

DIMACS Home Page