Zeitschriftenartikel:
M. Samer, St. Szeider:
"Algorithms for Propositional Model Counting";
Journal of Discrete Algorithms,
8
(2010),
1;
S. 50
- 64.
Kurzfassung englisch:
We present algorithms for the propositional model counting problem #SAT. The algorithms utilize tree decompositions of certain graphs associated with the given CNF formula; in particular we consider primal, dual, and incidence graphs. We describe the algorithms coherently for a direct comparison and with sufficient detail for making an actual implementation reasonably easy. We discuss several aspects of the algorithms including worst-case time and space requirements.
"Offizielle" elektronische Version der Publikation (entsprechend ihrem Digital Object Identifier - DOI)
http://dx.doi.org/10.1016/j.jda.2009.06.002
Zugeordnete Projekte:
Projektleitung Stefan Szeider:
Parametrisierte Komplexität Lokaler Suche
Erstellt aus der Publikationsdatenbank der Technischen Universität Wien.