A simple sub-quadratic algorithm for computing the subset partial order

DOI10.1016/0020-0190(95)00165-4zbMath0875.68463OpenAlexW2069684871MaRDI QIDQ672836

Paul A. Pritchard

Publication date: 28 February 1997

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(95)00165-4

zbMATH Keywords

AlgorithmsExtremal setsLexicographic orderSet-theoretic algorithmsSubset graphSubset partial order

Mathematics Subject Classification ID

Parallel algorithms in computer science (68W10)

Related Items (6)

Best match graphs ⋮ On the size of the subset partial order ⋮ Positional Dominance: Concepts and Algorithms ⋮ On the complexity of strongly connected components in directed hypergraphs ⋮ Computing the subset partial order for dense families of sets ⋮ Minimal approximate hitting sets and rule templates

Cites Work

• An old sub-quadratic algorithm for finding extremal sets
• Opportunistic algorithms for eliminating supersets
• A fast bit-parallel algorithm for computing the subset partial order
• Finding extremal sets in less than quadratic time
• On the computational power of pushdown automata
• Three Partition Refinement Algorithms
• Dynamic Perfect Hashing: Upper and Lower Bounds
• On Computing the Subset Graph of a Collection of Sets

This page was built for publication: A simple sub-quadratic algorithm for computing the subset partial order