Transformations on Regular Non-Dominated Coteries and Their Application (Algorithm Engineering as a New Paradigm)
Kazuhisa Makino, Tiko Kameda · Institutional Repositories DataBase (IRDB) · 2001
A coterie under an underlying set $U$ is a family of subsets of $U$ such that every pair of subsets has at least one element in common but neither is a subset of the other.A coterie $C$ under $U$ is said to be non-dominated $(\mathrm{N}\mathrm{D})$ if there is no other coterie $D$ under $U$ such that, for $\forall Q\in C$ , there exists $Q'\in D$ satisfying $Q'\subseteq Q$ .We introduce the operation $\sigma$ which transforms a ND coterie to another ND coterie.A regular coterie is a natural generalization of a vote-assignable coterie.We show that any regular ND coterie $C$ can be transformed to any other regular ND coterie $D$ by judiciously applying the a operation to $C$ at most $|C|+|D|-2$ times.As another application of the a operation, we present an incrementally polynomial-time algorithm for generating all regular ND coteries.We then introduce the concept of g-regular functional, as a generalization of availability.We show how to construct an optimum coterie $C$ with respect to a $\mathrm{g}$ -regular function in $O(n^{3}|C|)$ time, where $n=|U|$ .Finally, we discuss the structures of optimum coteries with respect to a $\mathrm{g}$ -regular functional.