Polynomial-time algorithms for regular set-covering and threshold synthesis
From MaRDI portal
Publication:1089348
DOI10.1016/0166-218X(85)90040-XzbMath0619.05020OpenAlexW1969423858MaRDI QIDQ1089348
Publication date: 1985
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0166-218x(85)90040-x
Related Items
An \(O(nm)\)-time algorithm for computing the dual of a regular Boolean function, Dual-bounded generating problems: Weighted transversals of a hypergraph, Dualization of regular Boolean functions, Decompositions of positive self-dual Boolean functions, An O(m n) algorithm for regular set-covering problems, Boolean minors, Trading transforms of non-weighted simple games and integer weights of weighted simple games, A special case of set covering problems, On the geometric separability of Boolean functions, Joint realizability of monotone Boolean functions, Forms of representation for simple games: sizes, conversions and equivalences, On the characterization of weighted simple games, Incremental polynomial time dualization of quadratic functions and a subclass of degree-\(k\) functions, Minimum self-dual decompositions of positive dual-minor Boolean functions, On the complexity of problems on simple games, Total domishold graphs: a generalization of threshold graphs, with connections to threshold hypergraphs, Sets uniquely determined by projections on axes. II: Discrete case, Enumeration of weighted games with minimum and an analysis of voting power for bipartite complete games with minimum, Generating all minimal integral solutions to AND-OR systems of monotone inequalities: Conjunctions are simpler than disjunctions, Computational aspects of monotone dualization: a brief survey, Simple games versus weighted voting games: bounding the critical threshold value, Counting and enumerating aggregate classifiers, Monotone clutters, On minimum sum representations for weighted voting games, Generating dual-bounded hypergraphs, A note on the growth of the dimension in complete simple games, Tree-shellability of Boolean functions, Linear separation of connected dominating sets in graphs, Decomposing 1-Sperner hypergraphs, On the Complexity of the Decisive Problem in Simple and Weighted Games, The threshold order of a Boolean function, Efficient dualization of \(O(\log n\))-term monotone disjunctive normal forms
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A new polynomial-time algorithm for linear programming
- A characterization of threshold matroids
- On the unimodality of some partition polynomials
- Generating All Maximal Independent Sets: NP-Hardness and Polynomial-Time Algorithms
- Weyl Groups, the Hard Lefschetz Theorem, and the Sperner Property
- Coefficient reduction for inequalities in 0–1 variables
- Faces for a linear inequality in 0–1 variables
- On Dedekind's Problem: The Number of Isotone Boolean Functions. II
- An Algorithm to Dualize a Regular Switching Function
- Regular (2, 2)-systems
- Solution of Two Difficult Combinatorial Problems with Linear Algebra
- Bottleneck extrema
