|
|
|
|
Литература
|
|
| |
| 1. |
J. M. Byskov, B. A. Madsen, B. Skjernaa, “New Algorithms for Exact Satisfiability”, Theoret. Comput. Sci., 332:1-3 (2005), 515–541    |
| 2. |
N. Bansal, V. Raman, “Upper Bounds for MaxSat: Further Improved”, Proceedings of ISAAC'99, 1999, 247–258 |
| 3. |
J. Chen, I. Kanj, Improved exact algorithms for MAX-SAT (to appear) |
| 4. |
М. А. Всемирнов, Э. А. Гирш, Е. Я. Данцин, С. В. Иванов, “Алгоритмы для пропозициональной выполнимости и верхние оценки их
сложности”, Зап. научн. семин. ПОМИ, 277, 2001, 14–46  |
| 5. |
M. Davis, G. Logemann, D. Loveland, “A machine program for theorem-proving”, Comm. ACM, 5 (1962), 394–397 |
| 6. |
А. С. Куликов, С. С. Федин, “Решение задачи о максимальном сечении за время $2^{|E|/4}$”, Зап. научн. семин. ПОМИ, 293, 2002, 129–138 |
| 7. |
J. Gramm, J. Guo, F. Hüffner, R. Niedermeier, “Automated Generation of Search Tree Algorithms for Hard Graph Modification Problems Algorithmica”, Algorithmica, 39:4 (2004), 321–347 |
| 8. |
J. Gramm, E. A. Hirsch, R. Niedermeier, P. Rossmanith, “New worst-case upper bounds for MAX-2-SAT with application to MAX-CUT”, Discrete Applied Mathematics, 130:2 (2003), 139–155 |
| 9. |
E. A. Hirsch, “New worst-case upper bounds for SAT”, J. Automated Reasoning, 24:4 (2000), 397–420 |
| 10. |
А. С. Куликов, “Верхняя оценка $O(2^{0.16254n})$ для { X$3$SAT}: более простое
доказательство”, Зап. научн. семин. ПОМИ, 293, 2002, 118–128 |
| 11. |
O. Kullmann, H. Luckhardt, “Algorithms for SAT/TAUT decision based on various measures”, Informatics and Computation, 1998 (to appear) |
| 12. |
S. I. Nikolenko, A. V. Sirotkin, “Worst-case upper bounds for SAT: automated proof”, Proceedings of the 8th ESSLLI Student Session, 2003, 225–232 |
| 13. |
V. Raman, B. Ravikumar, S. Srinivasa Rao, “A Simplified NP-complete MAXSAT Problem”, Information Processing Letters, 65 (1998), 1–6 |
