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)

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

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