Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > MARTIN FURER:
All reports by Author Martin Furer:

TR05-033 | 5th March 2005
Martin Furer, Shiva Prasad Kasiviswanathan

Algorithms for Counting 2-SAT Solutions and Colorings with Applications

An algorithm is presented for counting the number of maximum weight satisfying assignments of a 2SAT formula. The worst case running time of $O(\mbox{poly($n$)} \cdot 1.2461^n)$ for formulas with $n$ variables improves on the previous bound of $O(\mbox{poly($n$)} \cdot 1.2561^n)$ by Dahll\"of, Jonsson, and Wahlstr\"om . The weighted 2SAT counting ... more >>>




ISSN 1433-8092 | Imprint