Left-to-right multiplication for monotone Boolean dualization

DOI10.1137/080734881MaRDI QIDQ5390600zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Endre Boros, Kazuhisa Makino, Khaled Elbassioni

Publication date 4 April 2011

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/080734881

zbMATH Keywords

dualizationenumerating minimal hypergraph transversalsmonotone Boolean function

Mathematics Subject Classification ID

Boolean functions (06E30) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• On the Complexity of the Multiplication Method for Monotone CNF/DNF Dualization
• On Berge Multiplication for Monotone Boolean Dualization
• Computational aspects of monotone dualization: a brief survey
• Efficient dualization of \(O(\log n\))-term monotone disjunctive normal forms
• Monotone Boolean dualization is in co-NP\([\log^{2}n]\).

Cited in

(3)

• Efficient dualization of \(O(\log n\))-term monotone disjunctive normal forms
• The minimal hitting set generation problem: algorithms and computation
• On Berge Multiplication for Monotone Boolean Dualization

This page was built for publication: Left-to-right multiplication for monotone Boolean dualization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5390600)