Minimal unsatisfiable formulas with bounded clause-variable difference are fixed-parameter tractable
type: Item
instance of: scholarly article
title: Minimal unsatisfiable formulas with bounded clause-variable difference are fixed-parameter tractable
zbMATH Open document ID: 1108.68065
author: Stefan Szeider
published in: Journal of Computer and System Sciences
publication date: 2005-02-23T00:00:00Z
full work available at URL: 610.pdf
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68Q15
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 2137325
zbMATH Keywords: SAT problem
zbMATH Keywords: Minimal unsatisfiability
zbMATH Keywords: Fixed-parameter complexity
zbMATH Keywords: \(D^P\)-complete problem
zbMATH Keywords: Tree-width
zbMATH Keywords: Bipartite matching
zbMATH Keywords: Expansion
MaRDI profile type: Publication
OpenAlex ID: W2133544949
Wikidata QID: Q60060024
cites work: Minimal non-two-colorable hypergraphs and minimal unsatisfiable formulas
cites work: Satisfiability, branch-width and Tseitin tautologies
cites work: Complexity of Finding Embeddings in a k-Tree
cites work: On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic
cites work: Upper bounds to the clique width of graphs
cites work: A machine program for theorem-proving
cites work: A Computing Procedure for Quantification Theory
cites work: An efficient algorithm for the minimal unsatisfiability problem for a subclass of CNF
cites work: Q4947393
cites work: Q4503944
cites work: Graph-Theoretic Concepts in Computer Science
cites work: Polynomial-time recognition of minimal unsatisfiable formulas with fixed clause-variable difference.
cites work: An algorithm for the class of pure implicational formulas
cites work: A perspective on certain polynomial-time solvable classes of satisfiability
cites work: Fixed-parameter complexity in AI and nonmonotonic reasoning
cites work: Improving a fixed parameter tractability time bound for the shadow problem
cites work: Q4263797
cites work: On subclasses of minimal unsatisfiable formulas
cites work: Lean clause-sets: Generalizations of minimally unsatisfiable clause-sets
cites work: Matching theory
cites work: Solving satisfiability in less than \(2^ n\) steps
cites work: Q3221403
cites work: The complexity of facets resolved
cites work: Graph minors. V. Excluding a planar graph
cites work: Call routing and the ratcatcher
cites work: Generalizations of matched CNF formulas
cites work: Theory and Applications of Satisfiability Testing
cites work: A simplified NP-complete satisfiability problem
cites work: The Complexity of Propositional Proofs
cites work: Q4804883
DOI: 10.1016/J.JCSS.2004.04.009
description: scientific article; zbMATH DE number 2137325