Satisfiability of Acyclic and Almost Acyclic CNF Formulas.

DOI10.4230/LIPIcs.FSTTCS.2010.84zbMath1245.68112OpenAlexW2287549241MaRDI QIDQ2908839

Sebastian Ordyniak, Daniël Paulusma, Stefan Szeider

Publication date: 29 August 2012

Full work available at URL: http://subs.emis.de/LIPIcs/frontdoor_60ba.html

zbMATH Keywords

satisfiabilityparameterized complexitybackdoor setschordal bipartite graphs\(\beta\)-acyclic hypergraphs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

Backdoors to Satisfaction, Satisfiability of Acyclic and almost Acyclic CNF Formulas (II)