On variable-weighted exact satisfiability problems

1. Aho, A.V., Ganapathi, M., Tjiang, S.W.: Code generation using tree matching and dynamic programming. ACM Trans. Program. Lang. Syst. 11, 491–516 (1989)

   Article  Google Scholar 

2. Applegate, D., Cook, W.: Solving large-scale matching problems. In: Johnson, D.S., McGeoch, C.C. (eds.) Algorithms for Network Flows and Matching Theory, pp. 557–576. American Mathematical Society (1993)

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

   Article  MATH  MathSciNet  Google Scholar 

4. Byskov, J.M., Ammitzboll Madsen, B., Skjernaa, B.: New algorithms for exact satisfiability. Theor. Comp. Sci. 332, 515–541 (2005)

   Article  MATH  Google Scholar 

5. Cook, S.A.: The complexity of theorem proving procedures. In: Proceedings of the 3rd ACM Symposium on Theory of Computing, pp. 151–158. (1971)

6. 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)

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

   Article  MATH  Google Scholar 

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

   MATH  Google Scholar 

9. Liao, S., Kreutzer, K., Tjiang, S.W., Devadas, S.: A new viewpoint on code generation for directed acyclic graphs. ACM Transact. Des. Automat. Electron. Syst. 3, 51–75 (1998)

   Article  Google Scholar 

10. Le Berre D., Simon, L.: The essentials of the SAT 2003 competition. In: Proceedings of the 6th International Conference on Theory and Applications of Satisfiability Testing (SAT’03), Lecture Notes in Computer Science, vol. 2919, pp. 172–187. Springer (2004)

11. Monien, B., Speckenmeyer, E., Vornberger, O.: Upper bounds for covering problems. Methods Oper. Pes. 43, 419–431 (1981)

    MATH  MathSciNet  Google Scholar 

12. Papadimitriou, C.H.: Computational Complexity. Addison-Wesley (1994)

13. Plagge, G.: Über Variablen-Gewichtete X3SAT Optimierungs-Probleme. Diploma Thesis, Univ. Köln (2006)

14. Plagge, G., Porschen, S.: Solving optimum variable-weight Exact 3-Satisfiability in O(2^0.16254n) time. Techn. Report, Univ. Köln, (2007) (in press)

15. Porschen, S.: On some weighted satisfiability and graph problems. In: Proceedings of the 31st Conference on Current Trends in Theory and Practice of Informatics (SOFSEM 2005). Lecture Notes in Comp. Science, vol. 3381, pp. 278–287. Springer (2005)

16. Porschen, S.: Solving minimum weight exact satisfiability in O(2^{0.2441 n}) time. In: Proceedings of the 16th International Symposium on Algorithms and Computation (ISAAC 2005). Lecture Notes in Comp. Science, vol. 3827, pp. 654–664. Springer (2005)

17. Porschen, S.: Counting all solutions of minimum weight exact satisfiability. In: Proceedings of the 6th Italian Conference on Algorithms and Complexity (CIAC 2006). Lecture Notes in Comp. Science, vol. 3998, pp. 50–59. Springer (2006)

18. Porschen, S., Randerath, B., Speckenmeyer, E.: Exact 3-Satisfiability is Decidable in Time O(2^0.16254n). Ann. Math. Artif. Intell. 43, 173–193 (2005)

    MATH  MathSciNet  Google Scholar 

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

20. Valiant, L.: The complexity of computing the permanent. Theor. Comp. Sci. 8, 189–201 (1979)

    Article  MATH  MathSciNet  Google Scholar 

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

    Article  MathSciNet  Google Scholar 

Download references