Abstract: Some previously proposed algorithms of the author are re-examined. They were designed to find all sets in a collection that have no subset in the collection, but are easily modified to find all sets that have no supersets. One is shown to have a worst-case running time of O(N2 / log N), where N is the sum of the sizes of all the sets. This is lower than the only previously known sub-quadratic worst-case upper bound for this problem.
LFCS report ECS-LFCS-94-301, August 1994.
A revised verision has been submitted to Information Processing Letters.
Previous | Index | Next An error occured whilst processing this directive