Journal of the ACM Bibliography

Thomas Lengauer and Robert E. Tarjan. Asymptotically tight bounds on time-space trade-offs in a pebble game. Journal of the ACM, 29(4):1087-1130, October 1982. [BibTeX entry]
Categories and Subject Descriptors: F.1.3 [Computation by Abstract Devices]: Complexity Classes -- relations among complexity classes; F.2.3 [Analysis of Algorithms and Problem Complexity]: Tradeoffs among Complexity Measures; G.2.2 [Discrete Mathematics]: Graph Theory

General Terms: Algorithms, Theory

Additional Key Words and Phrases: Lower bounds, pebble game, superconcentrators

Selected references


  • Journal of the ACM homepage
  • Bibliography top level
  • Journal of the ACM Author Index
  • Search the HBP database