On the frequency of the most frequently occurring variable in dual monotone DNFs

DOI10.1016/S0012-365X(96)00090-8zbMath0872.06012MaRDI QIDQ1357747

Leonid G. Khachiyan, Vladimir A. Gurvich

Publication date: 6 October 1997

Published in: Discrete Mathematics (Search for Journal in Brave)

zbMATH Keywords

dualitydisjunctive normal formblockercluttertransversal hypergraphmonotone Boolean functionprime implicantsquasi-polynomial timefrequent variableshort implicant

Mathematics Subject Classification ID

Related Items (6)

Dual-bounded generating problems: Weighted transversals of a hypergraph ⋮ Lower Bounds for Three Algorithms for the Transversal Hypergraph Generation ⋮ Computational aspects of monotone dualization: a brief survey ⋮ Scientific contributions of Leo Khachiyan (a short overview) ⋮ Generating dual-bounded hypergraphs ⋮ Lower bounds for three algorithms for transversal hypergraph generation

Cites Work

• On 3-chromatic hypergraphs
• On the Complexity of Dualization of Monotone Disjunctive Normal Forms
• ON THE TWO-COLOURING OF HYPERGRAPHS

This page was built for publication: On the frequency of the most frequently occurring variable in dual monotone DNFs