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