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

Martin Furer, Shiva Prasad Kasiviswanathan

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 >>>