Generalizations of matched CNF formulas
type: Item
instance of: scholarly article
title: Generalizations of matched CNF formulas
zbMATH Open document ID: 1099.68044
author: Stefan Szeider
published in: Annals of Mathematics and Artificial Intelligence
publication date: 2005-05-13T00:00:00Z
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 68T20
zbMATH DE Number: 2168195
zbMATH Keywords: SAT problem
zbMATH Keywords: bipartite graph
zbMATH Keywords: matched formula
zbMATH Keywords: deficiency
zbMATH Keywords: biclique cover
zbMATH Keywords: NP-completeness
zbMATH Keywords: polynomial hierarchy
MaRDI profile type: Publication
full work available at URL: s10472-005-0432-6
OpenAlex ID: W4237683073
cites work: Minimal non-two-colorable hypergraphs and minimal unsatisfiable formulas
cites work: Q4947393
cites work: Q4503944
cites work: Complexity results for some eigenvector problems
cites work: Polynomial-time recognition of minimal unsatisfiable formulas with fixed clause-variable difference.
cites work: A perspective on certain polynomial-time solvable classes of satisfiability
cites work: Q4198056
cites work: Graph packings
cites work: Q4488342
cites work: Satisfiable formulas closed under replacement
cites work: Investigations on autark assignments
cites work: Lean clause-sets: Generalizations of minimally unsatisfiable clause-sets
cites work: Matching theory
cites work: Q4298260
cites work: The polynomial-time hierarchy
cites work: Minimal Unsatisfiable Formulas with Bounded Clause-Variable Difference are Fixed-Parameter Tractable
cites work: A simplified NP-complete satisfiability problem
DOI: 10.1007/S10472-005-0432-6
description: scientific article; zbMATH DE number 2168195