[Zurück]


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.