EDP Sciences logo
Subscriber Authentication Point
Search
Menu
All issues Volume 33 / No 1 (January Fabruary 1999) RAIRO-Theor. Inf. Appl., 33 1 (1999) 33-45 References
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). [Google Scholar]
  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] [Google Scholar]
  3. S.A. Cook, An Observation on time-storage trade-offs. J. Comp. Syst. Sci. 9 (1974) 308-316. [CrossRef] [Google Scholar]
  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. [Google Scholar]
  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). [Google Scholar]
  6. R. Greenlaw, H.J. Hoover and W.L. Ruzzo, Limits to parallel computation: P-completeness theory. Oxford University Press (1995). [Google Scholar]
  7. J. Hoover and W. Ruzzo, A compendium of problems complete for P. Manuscript (1984). [Google Scholar]
  8. N.D. Jones and T. Laaser, Complete problems for deterministic polynomial time. Theoret. Comput. Sci. 3 (1977) 105-117. [CrossRef] [Google Scholar]
  9. D.E. Knuth, The art of computer programming, Vol. 1. Addison-Wesley (1973). [Google Scholar]
  10. D. Kozen, Complexity of finitely presented algebras; in Proc. of 9th ACM STOC (1977) 164-167. [Google Scholar]
  11. R.E. Ladner, The circuit value problem is logspace complete for P. SIGACT News 7 (1975) 18-20. [CrossRef] [Google Scholar]
  12. M. Serna, The parallel approximbility of P-complete problems. PhD thesis, Universitat Politècnica de Catalunya (1990). [Google Scholar]
  13. M. Serna, Approximating linear programming is logspace complete for P. Inform. Proc. Lett. 37 (1991) 233-236. [CrossRef] [MathSciNet] [Google Scholar]
  14. S. Sahni and T. Gonzalez, P-complete approximation problems. J. Assoc. Comput. Mach. 23 (1976) 555-565. [Google Scholar]
  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. [Google Scholar]
  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. [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.