On generating all solutions of generalized satisfiability problems
Creignou, N. ; Hebrard, J.-J.
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 31 (1997), p. 499-511 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)
Publié le : 1997-01-01
@article{ITA_1997__31_6_499_0,
     author = {Creignou, N. and Hebrard, J.-J.},
     title = {On generating all solutions of generalized satisfiability problems},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {31},
     year = {1997},
     pages = {499-511},
     mrnumber = {1607518},
     zbl = {0901.68075},
     language = {en},
     url = {http://dml.mathdoc.fr/item/ITA_1997__31_6_499_0}
}

Creignou, N.; Hebrard, J.-J. On generating all solutions of generalized satisfiability problems. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 31 (1997) pp. 499-511. http://gdmltest.u-ga.fr/item/ITA_1997__31_6_499_0/

1. B. Aspvall, M. F. Plass and R. E. Tarjan, A linear-time algorithm for testing the truth of certain quantified boolean formulas, Information Processing Letters, 1979, 8, (3), pp. 121-123. | MR 526451 | Zbl 0398.68042

2. S. A. Cook, The complexity of theorem-proving procedures. In Third Annual ACM Symposium on Theory of Computing, 1971, pp. 151-158. | Zbl 0253.68020

3. N. Creignou and M. Hermann, Complexity of Generalized Satisfiability Counting Problems, Information and Computation, 1996, 125, (1), pp. 1-12. | MR 1385804 | Zbl 0853.68110

4. W. F. Dowling and J. H. Gallier, Linear-time algorithms for testing the satisfiability of propositional Horn formulæ, Journal of Logic Programming, 1984, 3, pp. 267-284. | MR 770156 | Zbl 0593.68062

5. M. R. Garey and D. S. Johnson, Computers and intractability: A guide to the theory of NP-completeness, W. H. Freeman and Co, 1979. | MR 519066 | Zbl 0411.68039

6. P. Hell and J. Nešetřil, On the complexity of H-coloring, Journal of Combinatorial Theory, Series B, 1990, 48, pp. 92-110. | MR 1047555 | Zbl 0639.05023

7. A. Horn, On sentences which are true of direct unions of algebras, Journal of Symbolic Logic, 1951, 16, pp. 14-21. | MR 40233 | Zbl 0043.24801

8. D. S. Johnson, M. Yannakakis and C. H. Papadimitriou, On generating all maximal independent sets, Information Processing Letters, 1988, 27, pp. 119-123. | MR 933271 | Zbl 0654.68086

9. R. E. Ladner, On the structure of polynomial time reducibility, Journal of the Association for Computing Machinery, 1975, 22, pp. 155-171. | MR 464698 | Zbl 0322.68028

10. A. K. Mackworth, Constraint Satisfaction, in S. C. Shapiro, ed., The encyclopedia of Artificial Intelligence, Wiley, New York, 1992, pp. 285-293. | MR 1192394

11. T. J. Schaefer, The complexity of satisfiability problems. In Proceedings 10th STOC, San Diego (CA, USA), Association for Computing Machinery, 1978, pp. 216-226. | MR 521057

12. L. G. Valiant, The complexity of enumeration and reliability problems, SIAM Journal on Computing, 1979, 8, (3), pp. 410-421. | MR 539258 | Zbl 0419.68082