Counting All Solutions of Minimum Weight Exact Satisfiability

1. Aspvall, B., Plass, M.R., Tarjan, R.E.: A linear-time algorithm for testing the truth of certain quantified Boolean formulas. Inform. Process. Lett. 8, 121–123 (1979)

   Article  MATH  MathSciNet  Google Scholar 

2. Dahllöf, V., Jonsson, P.: An Algorithm for Counting Maximum Weighted Independent Sets and its Applications. In: Proceedings of the 13th ACM-SIAM Symposium on Discrete Algorithms, pp. 292–298 (2002)

   Google Scholar 

3. Dahllöf, V., Jonsson, P., Beigel, R.: Algorithms for four variants of the exact satisfiability problem. Theoretical Comp. Sci. 320, 373–394 (2004)

   Article  MATH  Google Scholar 

4. Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman and Company, San Francisco (1979)

   MATH  Google Scholar 

5. Johnson, D.S., Yannakakis, M., Papadimitriou, C.H.: On Generating All Maximal Independent Sets. Inform. Process. Lett. 27, 119–123 (1988)

   Article  MATH  MathSciNet  Google Scholar 

6. Monien, B., Speckenmeyer, E., Vornberger, O.: Upper Bounds for Covering Problems. Methods of Operations Research 43, 419–431 (1981)

   MATH  MathSciNet  Google Scholar 

7. Porschen, S.: On Some Weighted Satisfiability and Graph Problems. In: Vojtáš, P., Bieliková, M., Charron-Bost, B., Sýkora, O. (eds.) SOFSEM 2005. LNCS, vol. 3381, pp. 278–287. Springer, Heidelberg (2005)

   Chapter  Google Scholar 

8. Porschen, S.: Solving Minimum Weight Exact Satisfiability in Time O(2^0.2441n). In: Deng, X., Du, D.-Z. (eds.) ISAAC 2005. LNCS, vol. 3827, pp. 654–664. Springer, Heidelberg (2005)

   Chapter  Google Scholar 

9. Schaefer, T.J.: The complexity of satisfiability problems. In: Proceedings of the 10th ACM Symposium on Theory of Computing, pp. 216–226 (1978)

   Google Scholar 

10. Valiant, L.: The complexity of enumeration and reliability problems. SIAM J. Comput. 9, 410–421 (1979)

    Article  MathSciNet  Google Scholar 

Download references