GANIAN, Robert, Petr HLINĚNÝ a Jan OBDRŽÁLEK. Better algorithms for satisfiability problems for formulas of bounded rank-width. Fundamenta Informaticae. Poland: IOS Press, The Netherlands, 2013, roč. 123, č. 1, s. 59-76. ISSN 0169-2968. Dostupné z: https://dx.doi.org/10.3233/FI-2013-800. |
Další formáty:
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Ý a Jan OBDRŽÁLEK. Better algorithms for satisfiability problems for formulas of bounded rank-width. \textit{Fundamenta Informaticae}. Poland: IOS Press, The Netherlands, 2013, roč.~123, č.~1, s.~59-76. ISSN~0169-2968. Dostupné z: https://dx.doi.org/10.3233/FI-2013-800.
|