Better algorithms for satisfiability problems for formulas of bounded rank-width

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

We provide a parameterized polynomial algorithm for the propositional model counting problem #SAT, the runtime of which is single-exponential in the rank-width of a formula. Previo…