On generating all solutions of generalized satisfiability problems

N. Creignou; J.-J. Hebrard

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (1997)

  • Volume: 31, Issue: 6, page 499-511
  • ISSN: 0988-3754

How to cite

top

Creignou, N., and Hebrard, J.-J.. "On generating all solutions of generalized satisfiability problems." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 31.6 (1997): 499-511. <http://eudml.org/doc/92575>.

@article{Creignou1997,
author = {Creignou, N., Hebrard, J.-J.},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {generalized-satisfiability problems},
language = {eng},
number = {6},
pages = {499-511},
publisher = {EDP-Sciences},
title = {On generating all solutions of generalized satisfiability problems},
url = {http://eudml.org/doc/92575},
volume = {31},
year = {1997},
}

TY - JOUR
AU - Creignou, N.
AU - Hebrard, J.-J.
TI - On generating all solutions of generalized satisfiability problems
JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY - 1997
PB - EDP-Sciences
VL - 31
IS - 6
SP - 499
EP - 511
LA - eng
KW - generalized-satisfiability problems
UR - http://eudml.org/doc/92575
ER -

References

top
  1. 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. Zbl0398.68042MR526451
  2. 2. S. A. COOK, The complexity of theorem-proving procedures. In Third Annual ACM Symposium on Theory of Computing, 1971, pp. 151-158. Zbl0253.68020
  3. 3. N. CREIGNOU and M. HERMANN, Complexity of Generalized Satisfiability Counting Problems, Information and Computation, 1996, 125, (1), pp. 1-12. Zbl0853.68110MR1385804
  4. 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. Zbl0593.68062MR770156
  5. 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. Zbl0411.68039MR519066
  6. 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. Zbl0639.05023MR1047555
  7. 7. A. HORN, On sentences which are true of direct unions of algebras, Journal of Symbolic Logic, 1951, 16, pp. 14-21. Zbl0043.24801MR40233
  8. 8. D. S. JOHNSON, M. YANNAKAKIS and C. H. PAPADIMITRIOU, On generating all maximal independent sets, Information Processing Letters, 1988, 27, pp. 119-123. Zbl0654.68086MR933271
  9. 9. R. E. LADNER, On the structure of polynomial time reducibility, Journal of the Association for Computing Machinery, 1975, 22, pp. 155-171. Zbl0322.68028MR464698
  10. 10. A. K. MACKWORTH, Constraint Satisfaction, in S. C. Shapiro, ed., The encyclopedia of Artificial Intelligence, Wiley, New York, 1992, pp. 285-293. MR1192394
  11. 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. Zbl1282.68143MR521057
  12. 12. L. G. VALIANT, The complexity of enumeration and reliability problems, SIAM Journal on Computing, 1979, 8, (3), pp. 410-421. Zbl0419.68082MR539258

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.