On Linear CNF Formulas

DOI10.1007/11814948_22zbMath1138.68551OpenAlexW1536155927MaRDI QIDQ5756579

Stefan Porschen, Ewald Speckenmeyer, Bert Randerath

Publication date: 4 September 2007

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/11814948_22

zbMATH Keywords

NP-completenessLatin squarelinear hypergraphsatisfiabilityedge colouringlinear CNF formula

Mathematics Subject Classification ID

Hypergraphs (05C65) Orthogonal arrays, Latin squares, Room squares (05B15) Coloring of graphs and hypergraphs (05C15) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Classical propositional logic (03B05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

A CNF Class Generalizing Exact Linear Formulas ⋮ The Lovász Local Lemma and Satisfiability