• People
• Events
• Research

An Old Sub-Quadratic Algorithm for Finding Extremal Sets

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(N² / 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.