Free Access
Issue
RAIRO-Theor. Inf. Appl.
Volume 31, Number 6, 1997
Page(s) 499 - 511
DOI https://doi.org/10.1051/ita/1997310604991
Published online 01 February 2017
  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. [MR: 526451] [Zbl: 0398.68042] [Google Scholar]
  2. 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] [Google Scholar]
  3. 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] [Google Scholar]
  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. [MR: 770156] [Zbl: 0593.68062] [Google Scholar]
  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. [MR: 519066] [Zbl: 0411.68039] [Google Scholar]
  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. [MR: 1047555] [Zbl: 0639.05023] [Google Scholar]
  7. 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] [Google Scholar]
  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. [MR: 933271] [Zbl: 0654.68086] [Google Scholar]
  9. 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] [Google Scholar]
  10. 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] [Google Scholar]
  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. [Zbl: 1282.68143] [MR: 521057] [Google Scholar]
  12. 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] [Google Scholar]

Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.

Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.

Initial download of the metrics may take a while.