On computing the subset graph of a collection of sets

Let a given collection of sets have size N measured by the sum of the cardi nalities. Yellin and Jutla presented an algorithm which constructed the par tial order induced by the subset relation (a "subset graph") in a claimed O (N-2 / log N) operations over a dictionary ADT, and exhibited a collection whose subset graph had Theta(N-2 / log(2) N) edges. This paper first establ ishes a matching upper bound on the number of edges in a subset graph. It a lso presents a finer analysis of the algorithm, which confirms the claimed upper bound and shows it to be tight. A simple implementation requiring O(1 ) bit-parallel operations per ADT operation is presented, along with a Vari ant of the algorithm with an implementation requiring O(N-2 / log N) RAM op erations, (C) 1999 Academic Press.