Vorträge und Posterpräsentationen (mit Tagungsband-Eintrag):
F. Slivovsky, St. Szeider:
"Model Counting for Formulas of Bounded Clique-Width";
Vortrag: International Symposium on Algorithms and Computation (ISAAC),
Hong Kong;
16.12.2013
- 18.12.2013; in: "Algorithms and Computation: 24th International Symposium, ISAAC 2013",
L. Cai, S. Cheng, T. Lam (Hrg.);
Springer / LNCS,
8283
(2013),
ISBN: 978-3-642-45029-7;
S. 677
- 687.
Kurzfassung englisch:
We show that #SAT is polynomial-time tractable for classes of CNF formulas whose incidence graphs have bounded symmetric clique-width (or bounded clique-width, or bounded rank-width). This result strictly generalizes polynomial-time tractability results for classes of formulas with signed incidence graphs of bounded clique-width and classes of formulas with incidence graphs of bounded modular treewidth, which were the most general results of this kind known so far.
"Offizielle" elektronische Version der Publikation (entsprechend ihrem Digital Object Identifier - DOI)
http://dx.doi.org/10.1007/978-3-642-45030-3_63
Zugeordnete Projekte:
Projektleitung Stefan Szeider:
The Parameterized Complexity of Reasoning Problems
Erstellt aus der Publikationsdatenbank der Technischen Universität Wien.