[Back]


Publications in Scientific Journals:

M. Samer, St. Szeider:
"Algorithms for Propositional Model Counting";
Journal of Discrete Algorithms, 8 (2010), 1; 50 - 64.



English abstract:
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.


"Official" electronic version of the publication (accessed through its Digital Object Identifier - DOI)
http://dx.doi.org/10.1016/j.jda.2009.06.002



Related Projects:
Project Head Stefan Szeider:
Parametrisierte Komplexitšt Lokaler Suche


Created from the Publication Database of the Vienna University of Technology.