An \(O(nm)\)-time algorithm for computing the dual of a regular Boolean function

DOI10.1016/0166-218X(94)90215-1zbMath0802.90078OpenAlexW2056749900MaRDI QIDQ1327236

Uri N. Peled, Bruno Simeone

Publication date: 18 December 1994

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

Full work available at URL: https://doi.org/10.1016/0166-218x(94)90215-1

zbMATH Keywords

dualizing a positive Boolean functionHop-Skip-and-Jump algorithmset- covering

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Boolean programming (90C09)

Related Items

Dual-bounded generating problems: Weighted transversals of a hypergraph, Influence decision models: from cooperative game theory to social network analysis, Interior and exterior functions of Boolean functions, Forms of representation for simple games: sizes, conversions and equivalences, Interior and exterior functions of positive Boolean functions., A geometric connection to threshold logic via cubical lattices, Incremental polynomial time dualization of quadratic functions and a subclass of degree-\(k\) functions, On generating the irredundant conjunctive and disjunctive normal forms of monotone Boolean functions, A graph approach for fuzzy-rough feature selection, Computational aspects of monotone dualization: a brief survey, On the complexity of monotone dualization and generating minimal hypergraph transversals, Generating dual-bounded hypergraphs, On the fractional chromatic number of monotone self-dual Boolean functions, Linear separation of connected dominating sets in graphs, The complexity of dependency detection and discovery in relational databases, On the Complexity of the Decisive Problem in Simple and Weighted Games, Efficient dualization of \(O(\log n\))-term monotone disjunctive normal forms

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A new polynomial-time algorithm for linear programming
• Dualization of regular Boolean functions
• Polynomial-time algorithms for regular set-covering and threshold synthesis
• An O(m n) algorithm for regular set-covering problems
• A Class of Polynomially Solvable Set-Covering Problems
• An Algorithm to Dualize a Regular Switching Function