A fast bit-parallel algorithm for computing the subset partial order

A given collection of sets has a natural partial order induced by the subse t relation. Let the size N of the collection be defined as the sum of the c ardinalities of the sets that comprise it. Algorithms have recently been di scovered that compute the partial order in worst-case time O(N-2/log N). Th is paper gives implementations of a variant of a previously proposed algori thm which exploit bit-parallel operations on a RAM with Theta(log N)-bit wo rds. One is shown to have a worst-case complexity of O (N-2 log log N/log(2 ) N) operations. This is the first known o(N-2/log N) worst case or randomi zed expected running time for this problem.