Minimal non-two-colorable hypergraphs and minimal unsatisfiable formulas
From MaRDI portal
Publication:1087560
DOI10.1016/0097-3165(86)90060-9zbMath0611.05045OpenAlexW2015211698MaRDI QIDQ1087560
Publication date: 1986
Published in: Journal of Combinatorial Theory. Series A (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0097-3165(86)90060-9
transversal theoryKönig's duality theoremminimal non-two-colorable hypergraphminimal unsatisfiable formulae
Related Items (40)
On finding short resolution refutations and small unsatisfiable subsets ⋮ Sharp thresholds of graph properties, and the $k$-sat problem ⋮ An infinite version of Ryser's inequality ⋮ Smooth and sharp thresholds for random{k}-XOR-CNF satisfiability ⋮ Smooth and sharp thresholds for random{k}-XOR-CNF satisfiability ⋮ Disproof of the neighborhood conjecture with implications to SAT ⋮ On Davis-Putnam reductions for minimally unsatisfiable clause-sets ⋮ A new bound for 3-satisfiable MaxSat and its algorithmic application ⋮ The Discrepancy of Unsatisfiable Matrices and a Lower Bound for the Komlós Conjecture Constant ⋮ Are hitting formulas hard for resolution? ⋮ Irreducible subcube partitions ⋮ On the structure of some classes of minimal unsatisfiable formulas ⋮ Lean clause-sets: Generalizations of minimally unsatisfiable clause-sets ⋮ Homomorphisms of conjunctive normal forms. ⋮ Minimal non-odd-transversal hypergraphs and minimal non-odd-bipartite hypergraphs ⋮ On the Computational Complexity of Read once Resolution Decidability in 2CNF Formulas ⋮ 2000 European Summer Meeting of the Association for Symbolic Logic. Logic Colloquium 2000 ⋮ On Variables with Few Occurrences in Conjunctive Normal Forms ⋮ Finding the Hardest Formulas for Resolution ⋮ On Minimal Unsatisfiability and Time-Space Trade-offs for k-DNF Resolution ⋮ Finding read-once resolution refutations in systems of 2CNF clauses ⋮ Computational complexity of quantified Boolean formulas with fixed maximal deficiency ⋮ Fixed-parameter tractability of satisfying beyond the number of variables ⋮ A new lower bound on the maximum number of satisfied clauses in Max-SAT and its algorithmic applications ⋮ Minimal unsatisfiable formulas with bounded clause-variable difference are fixed-parameter tractable ⋮ Computing unsatisfiable \(k\)-SAT instances with few occurrences per variable ⋮ An upper bound for the circuit complexity of existentially quantified Boolean formulas ⋮ The complexity of homomorphisms and renamings for minimal unsatisfiable formulas ⋮ Generalizations of matched CNF formulas ⋮ Extension and equivalence problems for clause minimal formulae ⋮ A New Bound for 3-Satisfiable Maxsat and Its Algorithmic Application ⋮ The Lovász Local Lemma and Satisfiability ⋮ A branch and bound algorithm for extracting smallest minimal unsatisfiable subformulas ⋮ On subclasses of minimal unsatisfiable formulas ⋮ Investigations on autark assignments ⋮ Polynomial time algorithms for computing a representation for minimal unsatisfiable formulas with fixed deficiency. ⋮ Polynomial-time recognition of minimal unsatisfiable formulas with fixed clause-variable difference. ⋮ Space bounds for resolution ⋮ Irreducible disjoint covering systems (with an application to Boolean algebra) ⋮ A perspective on certain polynomial-time solvable classes of satisfiability
Cites Work
This page was built for publication: Minimal non-two-colorable hypergraphs and minimal unsatisfiable formulas
