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

Logo poskytovatele

Varování

Publikace nespadá pod Filozofickou fakultu, ale pod Fakultu informatiky. Oficiální stránka publikace je na webu muni.cz.
Autoři

GANIAN Robert HLINĚNÝ Petr OBDRŽÁLEK Jan

Rok publikování 2010
Druh Článek ve sborníku
Konference IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)
Fakulta / Pracoviště MU

Fakulta informatiky

Citace
www
Doi http://dx.doi.org/10.4230/LIPIcs.FSTTCS.2010.73
Obor Informatika
Klíčová slova propositional model counting; satisfiability; rank-width; clique-width; parameterized complexity
Popis 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. Previously, analogous algorithms have been known -- e.g.~[Fischer, Makowsky, and Ravve] -- with a single-exponential dependency on the clique-width of a formula. Our algorithm thus presents an exponential runtime improvement (since clique-width reaches up to exponentially higher values than rank-width), and can be of practical interest for small values of rank-width. We also provide an algorithm for the MAX-SAT problem along the same lines.
Související projekty:

Používáte starou verzi internetového prohlížeče. Doporučujeme aktualizovat Váš prohlížeč na nejnovější verzi.