| GANIAN, Robert, Petr HLINĚNÝ and Jan OBDRŽÁLEK. Better algorithms for satisfiability problems for formulas of bounded rank-width. Fundamenta Informaticae. Poland: IOS Press, The Netherlands, 2013, vol. 123, No 1, p. 59-76. ISSN 0169-2968. Available from: https://dx.doi.org/10.3233/FI-2013-800. |
Other formats:
BibTeX
LaTeX
RIS
@article{1123106,
author = {Ganian, Robert and Hliněný, Petr and Obdržálek, Jan},
article_location = {Poland},
article_number = {1},
doi = {http://dx.doi.org/10.3233/FI-2013-800},
keywords = {propositional model counting; satisfiability; rank-width; clique-width; parameterized complexity},
language = {eng},
issn = {0169-2968},
journal = {Fundamenta Informaticae},
title = {Better algorithms for satisfiability problems for formulas of bounded rank-width},
volume = {123},
year = {2013}
}
TY - JOUR
ID - 1123106
AU - Ganian, Robert - Hliněný, Petr - Obdržálek, Jan
PY - 2013
TI - Better algorithms for satisfiability problems for formulas of bounded rank-width
JF - Fundamenta Informaticae
VL - 123
IS - 1
SP - 59-76
EP - 59-76
PB - IOS Press, The Netherlands
SN - 01692968
KW - propositional model counting
KW - satisfiability
KW - rank-width
KW - clique-width
KW - parameterized complexity
N2 - 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.
ER -
GANIAN, Robert, Petr HLINĚNÝ and Jan OBDRŽÁLEK. Better algorithms for satisfiability problems for formulas of bounded rank-width. \textit{Fundamenta Informaticae}. Poland: IOS Press, The Netherlands, 2013, vol.~123, No~1, p.~59-76. ISSN~0169-2968. Available from: https://dx.doi.org/10.3233/FI-2013-800.
|
