Další formáty:
BibTeX
LaTeX
RIS
@inproceedings{904650, author = {Ganian, Robert and Hliněný, Petr and Obdržálek, Jan}, address = {Dagstuhl, Germany}, booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)}, doi = {http://dx.doi.org/10.4230/LIPIcs.FSTTCS.2010.73}, edition = {2010}, keywords = {propositional model counting; satisfiability; rank-width; clique-width; parameterized complexity}, howpublished = {elektronická verze "online"}, language = {eng}, location = {Dagstuhl, Germany}, isbn = {978-3-939897-23-1}, pages = {73-83}, publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, LIPICS}, title = {Better algorithms for satisfiability problems for formulas of bounded rank-width}, url = {http://dx.doi.org/10.4230/LIPIcs.FSTTCS.2010.73}, year = {2010} }
TY - JOUR ID - 904650 AU - Ganian, Robert - Hliněný, Petr - Obdržálek, Jan PY - 2010 TI - Better algorithms for satisfiability problems for formulas of bounded rank-width PB - Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, LIPICS CY - Dagstuhl, Germany SN - 9783939897231 KW - propositional model counting KW - satisfiability KW - rank-width KW - clique-width KW - parameterized complexity UR - http://dx.doi.org/10.4230/LIPIcs.FSTTCS.2010.73 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. Online. In \textit{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)}. 2010. vyd. Dagstuhl, Germany: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, LIPICS, 2010, s.~73-83. ISBN~978-3-939897-23-1. Dostupné z: https://dx.doi.org/10.4230/LIPIcs.FSTTCS.2010.73.
|