On Computing the Subset Graph of a Collection of Sets |
| |
Authors: | Paul Pritchard |
| |
Institution: | aSchool of Computing and Information Technology, Griffith University, Queensland, 4111, Australia |
| |
Abstract: | Let a given collection of sets have size N measured by the sum of the cardinalities. Yellin and Jutla presented an algorithm which constructed the partial order induced by the subset relation (a “subset graph”) in a claimed O(N2/log N) operations over a dictionary ADT, and exhibited a collection whose subset graph had Θ(N2/log2 N) edges. This paper first establishes a matching upper bound on the number of edges in a subset graph. It also 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 variant of the algorithm with an implementation requiring O(N2/log N) RAM operations. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|