GANIAN, Robert and Stefan SZEIDER. New Width Parameters for Model Counting. Online. In Serge Gaspers and Toby Walsh. Theory and Applications of Satisfiability Testing - {SAT} 2017 - 20th International Conference, Melbourne, VIC, Australia, August 28 - September 1, 2017, Proceedings. Nemecko: Springer, 2017, p. 38-52. ISBN 978-3-319-66262-6. Available from: https://dx.doi.org/10.1007/978-3-319-66263-3_3. |
Other formats:
BibTeX
LaTeX
RIS
@inproceedings{1414045, author = {Ganian, Robert and Szeider, Stefan}, address = {Nemecko}, booktitle = {Theory and Applications of Satisfiability Testing - {SAT} 2017 - 20th International Conference, Melbourne, VIC, Australia, August 28 - September 1, 2017, Proceedings}, doi = {http://dx.doi.org/10.1007/978-3-319-66263-3_3}, editor = {Serge Gaspers and Toby Walsh}, keywords = {Treewidth; Model Counting; SAT; Parameterized Complexity}, howpublished = {elektronická verze "online"}, language = {eng}, location = {Nemecko}, isbn = {978-3-319-66262-6}, pages = {38-52}, publisher = {Springer}, title = {New Width Parameters for Model Counting}, url = {https://link.springer.com/chapter/10.1007/978-3-319-66263-3_3#citeas}, year = {2017} }
TY - JOUR ID - 1414045 AU - Ganian, Robert - Szeider, Stefan PY - 2017 TI - New Width Parameters for Model Counting PB - Springer CY - Nemecko SN - 9783319662626 KW - Treewidth KW - Model Counting KW - SAT KW - Parameterized Complexity UR - https://link.springer.com/chapter/10.1007/978-3-319-66263-3_3#citeas L2 - https://link.springer.com/chapter/10.1007/978-3-319-66263-3_3#citeas N2 - We study the parameterized complexity of the propositional model counting problem #SAT for CNF formulas. As the parameter we consider the treewidth of the following two graphs associated with CNF formulas: the consensus graph and the conflict graph. Both graphs have as vertices the clauses of the formula; in the consensus graph two clauses are adjacent if they do not contain a complementary pair of literals, while in the conflict graph two clauses are adjacent if they do contain a complementary pair of literals. We show that #SAT is fixed-parameter tractable for the treewidth of the consensus graph but W[1]-hard for the treewidth of the conflict graph. We also compare the new parameters with known parameters under which #SAT is fixed-parameter tractable. ER -
GANIAN, Robert and Stefan SZEIDER. New Width Parameters for Model Counting. Online. In Serge Gaspers and Toby Walsh. \textit{Theory and Applications of Satisfiability Testing - $\{$SAT$\}$ 2017 - 20th International Conference, Melbourne, VIC, Australia, August 28 - September 1, 2017, Proceedings}. Nemecko: Springer, 2017, p.~38-52. ISBN~978-3-319-66262-6. Available from: https://dx.doi.org/10.1007/978-3-319-66263-3\_{}3.
|