Free Access
Issue
RAIRO-Theor. Inf. Appl.
Volume 33, Number 1, January Fabruary 1999
Page(s) 33 - 45
DOI https://doi.org/10.1051/ita:1999104
Published online 15 August 2002
  1. J.L. Balcázar, J. Díaz and J. Gabarró, Structural complexity II, Springer Verlag (1995).
  2. N. Calkin and A. Frieze, Probabilistic analysis of a parallel algorithm for finding a maximal independent set. Random Structures and Algorithms 1 (1990) 39-50. [CrossRef] [MathSciNet]
  3. S.A. Cook, An Observation on time-storage trade-offs. J. Comp. Syst. Sci. 9 (1974) 308-316. [CrossRef]
  4. D. Coppersmith, P. Raghavan and M. Tompa, Parallel graph algorithms that are efficient in average, in Proc. of 28th IEEE Symposium on Foundations of Computer Science (1987) 260-269.
  5. J. Díaz, M. Serna, P. Spirakis and J. Torán, On the expected depth of Boolean circuits. Technical Report LSI-94-7-R, Universitat Politècnica de Catalunya, Dept. de LSI (1994).
  6. R. Greenlaw, H.J. Hoover and W.L. Ruzzo, Limits to parallel computation: P-completeness theory. Oxford University Press (1995).
  7. J. Hoover and W. Ruzzo, A compendium of problems complete for P. Manuscript (1984).
  8. N.D. Jones and T. Laaser, Complete problems for deterministic polynomial time. Theoret. Comput. Sci. 3 (1977) 105-117. [CrossRef]
  9. D.E. Knuth, The art of computer programming, Vol. 1. Addison-Wesley (1973).
  10. D. Kozen, Complexity of finitely presented algebras; in Proc. of 9th ACM STOC (1977) 164-167.
  11. R.E. Ladner, The circuit value problem is logspace complete for P. SIGACT News 7 (1975) 18-20. [CrossRef]
  12. M. Serna, The parallel approximbility of P-complete problems. PhD thesis, Universitat Politècnica de Catalunya (1990).
  13. M. Serna, Approximating linear programming is logspace complete for P. Inform. Proc. Lett. 37 (1991) 233-236. [CrossRef] [MathSciNet]
  14. S. Sahni and T. Gonzalez, P-complete approximation problems. J. Assoc. Comput. Mach. 23 (1976) 555-565. [CrossRef] [MathSciNet]
  15. M. Serna and P.G. Spirakis, The approximability of problems complete for P, in International Symposium on Optimal Algorithms, Springer-Verlag, Lecture Notes in Computer Science 401 (1989) 193-204.
  16. T. Tsukiji and F. Xhafa, On the expected depth of randomly generated circuits, J. Díaz and M. Serna Eds., in Proc. of Fourth European Symposium on Algorithms, ESA'96, Springer-Verlag, Lecture Notes in Computer Science 1136 (1996) 208-220.

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.