## On Computing the Subset Graph of a Collection of Sets

**Paul Pritchard**
*Abstract:* The extremal sets in a collection of sets are
those that either have no subset or have no superset in the
collection. Yellin and Jutla presented an algorithm for determining
the extremal sets by constructing the partial order induced by the
subset relation, which they called the ``subset graph''. This paper
presents alternative implementations of their algorithm that have
several advantages, including lower worst-case complexities. Also,
an upper bound is established on the maximal number of edges in a
subset graph of given size (measured by the sum of the
cardinalities of the sets at the vertices). This matches (up to a
constant factor) the lower bound constructed by Yellin and
Jutla.

*LFCS report ECS-LFCS-94-309,
October 1994.*

Previous |

Index |

Next