Better Algorithms for Satisfiability Problems for Formulas of Bounded Rank-width

DOI10.3233/FI-2013-800zbMath1280.68239MaRDI QIDQ4914311

Petr Hliněný, Jan Obdržálek, Robert Ganian

Publication date: 18 April 2013

Published in: Fundamenta Informaticae (Search for Journal in Brave)

zbMATH Keywords

satisfiabilityclique-widthparameterized complexityrank-widthpropositional model counting

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Related Items (10)

Community Structure Inspired Algorithms for SAT and #SAT ⋮ Model counting for CNF formulas of bounded modular treewidth ⋮ Parameterized complexity of envy-free resource allocation in social networks ⋮ Unnamed Item ⋮ On efficiently solvable cases of quantum \(k\)-SAT ⋮ New width parameters for SAT and \#SAT ⋮ The complexity landscape of decompositional parameters for ILP ⋮ On the complexity of finding large odd induced subgraphs and odd colorings ⋮ Using decomposition-parameters for QBF: mind the prefix! ⋮ Digraphs of Bounded Width

This page was built for publication: Better Algorithms for Satisfiability Problems for Formulas of Bounded Rank-width