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

Varování

Publikace nespadá pod Ústav výpočetní techniky, 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://www.fsttcs.org/
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:	Vysoce paralelní a distribuované výpočetní systémy Využití strukturálních a šířkových parametrů v kombinatorice a algoritmické složitosti Strukturální teorie grafů a parametrizovaná složitost Parameterized Algorithms and Width measures on Graphs Rozsáhlé výpočetní systémy: modely, aplikace a verifikace