New theoretical results on the monotone Boolean duality and the monotone Boolean dualization problems

DOI10.1016/J.DAM.2024.10.019MaRDI QIDQ6657241zbMATH OpenFDO

Authors Alice Raffaele, Romeo Rizzi

Publication date 6 January 2025

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

Full work available at URL https://doi.org/10.1016/J.DAM.2024.10.019

zbMATH Keywords

clutter and blockerdualizationfull coverhypergraph transversalmonotone Boolean functionquasi-polynomial time

Mathematics Subject Classification ID

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

Recommendations

• Computational aspects of monotone dualization: a brief survey
• Monotone Boolean dualization is in co-NP\([\log^{2}n]\).
• scientific article; zbMATH DE number 7286679
• On the complexity of monotone dualization and generating minimal hypergraph transversals
• Self-duality of bounded monotone Boolean functions and related problems

Cites work

• A Fast and Simple Parallel Algorithm for the Monotone Duality Problem
• A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra
• A Solution of the Shannon Switching Game
• Advances in Artificial Intelligence
• An efficient implementation of a quasi-polynomial algorithm for generating hypergraph transversals and its application in joint generation
• Bottleneck extrema
• Complexity of identification and dualization of positive Boolean functions
• Computational aspects of monotone dualization: a brief survey
• Double description method revisited
• Dual-Bounded Generating Problems: All Minimal Integer Solutions for a Monotone System of Linear Inequalities
• Dual-bounded generating problems: Partial and multiple transversals of a hypergraph
• Efficiently enumerating hitting sets of hypergraphs arising in data profiling
• Experimental comparison of the two Fredman-Khachiyan-algorithms
• scientific article; zbMATH DE number 5548206 (Why is no real title available?)
• scientific article; zbMATH DE number 43754 (Why is no real title available?)
• scientific article; zbMATH DE number 7286679 (Why is no real title available?)
• scientific article; zbMATH DE number 3078984 (Why is no real title available?)
• Identifying the Minimal Transversals of a Hypergraph and Related Problems
• Monotone Boolean dualization is in co-NP\([\log^{2}n]\).
• New Results on Monotone Dualization and Generating Hypergraph Transversals
• On the Complexity of Dualization of Monotone Disjunctive Normal Forms
• On the complexity of monotone dualization and generating minimal hypergraph transversals
• On the Complexity of Some Enumeration Problems for Matroids
• On the width—length inequality
• The complexity of facets (and some facets of complexity)
• The Forbidden Minors of Binary Clutters
• The vertex set of a \(0/1\)-polytope is strongly \(\mathcal P\)-enumerable

Cited in

(1)

• Monomial polarization and depolarization of abstract simplicial complexes

This page was built for publication: New theoretical results on the monotone Boolean duality and the monotone Boolean dualization problems

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