文章基本信息

标题：Better Algorithms for Satisfiability Problems for Formulas of Bounded Rank-width
本地全文：下载
作者：Robert Ganian ; Petr Hlinen{\'y ; Jan Obdrz{\'a}lek 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2010
卷号：8
页码：73-83
DOI：10.4230/LIPIcs.FSTTCS.2010.73
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：propositional model counting; satisfiability; rank-width; clique-width ; parameterized complexity