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]
  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]
  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]
  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]
  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]
  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]
  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]
  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]
  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]
  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]
  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]
  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]

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.