Minimal unsatisfiable formulas with bounded clause-variable difference are fixed-parameter tractable (Q1765303)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Minimal unsatisfiable formulas with bounded clause-variable difference are fixed-parameter tractable |
scientific article; zbMATH DE number 2137325
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Minimal unsatisfiable formulas with bounded clause-variable difference are fixed-parameter tractable |
scientific article; zbMATH DE number 2137325 |
Statements
Minimal unsatisfiable formulas with bounded clause-variable difference are fixed-parameter tractable (English)
0 references
23 February 2005
0 references
SAT problem
0 references
Minimal unsatisfiability
0 references
Fixed-parameter complexity
0 references
\(D^P\)-complete problem
0 references
Tree-width
0 references
Bipartite matching
0 references
Expansion
0 references
0 references
0 references
