A Fast and Simple Algorithm for Identifying 2-Monotonic Positive Boolean Functions

DOI10.1006/JAGM.1997.0896MaRDI QIDQ4386450zbMATH OpenOpenAlexFDO

Authors Kazuhisa Makino, Toshihide Ibaraki

Publication date 23 June 1998

Published in Journal of Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1006/jagm.1997.0896

zbMATH Keywords

maximum latency

Mathematics Subject Classification ID

Parallel algorithms in computer science (68W10)

Recommendations

• A fast and simple algorithm for identifying 2-monotonic positive Boolean functions
• Polynomial-Time Recognition of 2-Monotonic Positive Boolean Functions Given by an Oracle
• The Maximum Latency and Identification of Positive Boolean Functions

Cited in

(14)

• Guided inference of nested monotone Boolean functions
• Efficient dualization of \(O(\log n\))-term monotone disjunctive normal forms
• Dual-bounded generating problems: Weighted transversals of a hypergraph
• Complexity of identification and dualization of positive Boolean functions
• A linear time algorithm for recognizing regular Boolean functions
• Polynomial-Time Recognition of 2-Monotonic Positive Boolean Functions Given by an Oracle
• The Maximum Latency and Identification of Positive Boolean Functions
• Generating dual-bounded hypergraphs
• An incremental polynomial time algorithm to enumerate all minimal edge dominating sets
• Incremental polynomial time dualization of quadratic functions and a subclass of degree-\(k\) functions
• A fast and simple algorithm for identifying 2-monotonic positive Boolean functions
• Enumerating minimal dominating sets in chordal bipartite graphs
• Computational aspects of monotone dualization: a brief survey
• On the complexity of monotone dualization and generating minimal hypergraph transversals

This page was built for publication: A Fast and Simple Algorithm for Identifying 2-Monotonic Positive Boolean Functions

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