Thomas Lengauer
Robert E. Tarjan
- 1 CHANDRA, A.K.Effictent compilation of linear recurslve programs. 14th Ann. IEEE Syrup. on Switching and Automata Theory, Ames, Iowa, 1973, pp. 16-25.Google Scholar
- 2 COOK, S.A. An observation on time-storage trade-off. Z Comput. Syst. Sci. 9 (1974), 308-316.Google Scholar
- 3 COOK, S.A., AND SETHI, R.Storage requirements for determinisUc polynomial finite recognizable languages. J. Comput Syst. Sa. 13 (1976), 25-37Google Scholar
- 4 ERDos, P, GRAK~, R.L., AlqD Sz~mRF.DL E. On sparse graphs with dense long paths. Comp. Math. Appl. 1 (1975), 365-369.Google Scholar
- 5 GABBER, O., AND GALIL, Z.Exphctt constructmn of linear stze concentrators and superconcentrators. 20th Ann. IEEE Symp on Foundations of Computer Scmnce, San Juan, Puerto Rico, 1979, pp. 364-370.Google Scholar
- 6 GILBERT, J.R., LENGAtam, T., At~O T~AN, R.E.The pebbling problem is complete in polynomial space SIAM J Comput. 9 (1980), 513-524Google Scholar
- 7 GILBERT, J.R., AND TARJAN, R.E Variations of a pebble game on graphs. Tech. Pep No. 661, Computer Soence Dep., Stanford Univ, Stanford, Cahf, 1978. Google Scholar
- 8 HnwIrr, C.E, ^~D P^aXRSON, M.S.Comparative schematology Project MAC Conf. on Concurrent Systems and Parallel Computation, Woods Hole, Mass, 1970, pp. 119-127.Google Scholar
- 9 HOPCROFT, J., PAUL, W., AND VALIANT~ L On tune versus space. J A CM 24, 2 (Apr. 1977), 332-337. Google Scholar
- 10 JA'JA', J.Tine-space trade-offs for some algebraic problems. 12th Ann. ACM Syrup. on Theory of Computing, Los Angeles, Cahf., 1980, pp 339-350. Google Scholar
- 11 LENGAtmR, T, AND TAILIAN, R E.Upper and lower bounds on time-space trade-offs. 1 lth Ann ACM Symp. on Theory of Computing, Atlanta, Ga., 1979, pp. 262-277. Google Scholar
- 12 LINOAS, A,A P-space complete problem related to a pebble game In F~h Int. Colloq. on Automata, Languages and Programming, Lecture Notes m Computer Scaence 62, G. Ausldlo and C. Bohm, Eds., Spnnger-Verlag, New York, 1978, pp. 300-321. Google Scholar
- 13 Lool, M.C. A note on the pebble game Inf. Proc Lett. 11 (1980), 24--26Google Scholar
- 14 MARGULIS, G.A.Expliot construchons of concentrators. Problem), Peredachi Informatsii 9 (1973), 71-80 (English trans, in: Problems of Information Transmtss:on, Plenum, New York, 1975).Google Scholar
- 15 MEYER AUF DER HEIDE, F A comparison between two variations of a pebble game on graphs In 6th lnt. Colloq. on Automata, Languages and Programming, Lecture Notes m Computer Science 71, H A. Maurer, Ed, Springer-Vedag, New York, 1979, pp 411--421. Google Scholar
- 16 PALrL, W.J. On time hxerarehaes. 8th Ann ACM Symp. on Theory of Computing, Hershey, P~,., 1976, pp. 218-222Google Scholar
- 17 PAUL, W.J., AND REISCHUK, R.On alternation I1. A graph theoreuc approach to determinism versus nondetermmlsm Acta lnf 14 (1980), 391--403.Google Scholar
- 18 PAUL, W.J., AND TARJAN, R.E. Ttme-space trade-offs in a pebble game Acta. Inf 10 (1978), 111-115.Google Scholar
- 19 PAUL, W J., TARIAN, R.E., AND CELOr~I, J.R Space bounds for a game on graphs. Math. Syst. Theory I0 (1977), 239-251.Google Scholar
- 20 PINSKE~, M.S.On the complexity of a concentrator. Proc. 7th Int. Teletraffic Congress, Stockholm, 1973, pp. 318/1-318/4 (available from Secretariat, Televerket S-12386, Farsta, Sweden)Google Scholar
- 21 PlPPENGER, N.Superconcentrators. SlAM ~ ComImt. 6 (1977), 298-304.Google Scholar
- 22 PlPPENGER, N. A time-space trade-off. J ACM 25, 3 (July 1978), 509-5t5. Google Scholar
- 23 Pn, P~GER, N Comparattve schematology and pebbling with auxiliary pushdowns 12th Ann ACM Syrup. on Theory of Computing, Los Angeles, Calif., 1980, pp. 351-356. Google Scholar
- 24 I~tSCaUK, R.Improved bounds on the problem of time-space trade-off in the pebble game. ~ A CM 27, 4 (Oct. 1980), 839-850. Google Scholar
- 25 SCmCrrGER, G.A family of graphs with expenswe depth-reduction. Fakultat fur Mathemattk, Universttat Blelefeld, Bielefeld, W. Germany, 1980Google Scholar
- 26 SAVAGE, J.E., AND SWAMY, S.Space-time trade-offs on the FFT-algonthm. Tech. Rep. CS-31, Brown Univ., Providence, R.I., 1977.Google Scholar
- 27 SAVAGE, J.E., AND SWAMY, S. Space-trine trade-offs for integer multiphcation, 6th lnt. Colloq. on Automata, Languages and Programming, Lecture Notes in Computer Sctence 71, H A. Maurer, Ed, Springer-Verlag, New York, 1979, pp. 498-504. Google Scholar
- 28 SAVAGE, J.E,., AND SWAMY, S Space-me trade-offs for linear recurston. 6th ACM Symp on Principles of Programming Languages, San Antonio, Texas, 1979, pp 135-142. Google Scholar
- 29 SETm, R.Complete register allocation problems. SIAM~ Comput. 4 (1975), 226-248.Google Scholar
- 30 ToMPA, M,Time-space trade-offs for computing funettons, using cormectivtty properties of thetr circuits. 10th Ann. ACM Symp. on Theory of Computing, San Dtego, Cahf, 1978, pp. 196-204 Google Scholar
- 31 Tom, A, M.Two familiar transitive closure algorithms wluch admit no polynomial-time, sublinear space implementations. 12th Ann. ACM Syrup on Theory of Computing, Los Angeles, Cahf., 1980, pp. 333-338. Google Scholar
- 32 VALIAr~r, L.G Graph-theoretic propemes m computational complexity. ~ Comput. Syst. Sc~ 13 (1976), 278--285.Google Scholar
- 33 VALIANt, L.G.Graph-theoretic arguments m low level complexity. Symp. on Mathematwal Foundations of Computer Science, Lecture Notes in Computer Science 53, Sprmger-Verlag, New York, 1977, pp. 162-176Google Scholar
- 34 VAN EMDE-BoAs, P, AND VAN LEEUWEN, J. Move rules and trade-offs in the pebble game 4th GI Conf. on Theoretical Computer Science, Lecture Notes in Computer Science 67, G Goos and I. Hartmanis, Eds., Springer-Verlag, New York, 1979, pp. 101-112. Google Scholar
Index Terms
- Asymptotically tight bounds on time-space trade-offs in a pebble game
Recommendations
Time-space trade-offs for predecessor search
STOC '06: Proceedings of the thirty-eighth annual ACM symposium on Theory of ComputingWe develop a new technique for proving cell-probe lower bounds for static data structures. Previous lower bounds used a reduction to communication games, which was known not to be tight by counting arguments. We give the first lower bound for an ...
Time-space trade-offs for general recursion
SFCS '81: Proceedings of the 22nd Annual Symposium on Foundations of Computer ScienceA lower bound for the time-space trade-off of pebble games on PD-Graphs (which represent computations of push-down automata or recursion schemes) is proved, that is only a bit lower than the best known upper bound (the lower and upper time bound is ...
Optimal time-space trade-offs for non-comparison-based sorting
SODA '02: Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithmsWe study the problem of sorting n integers of w bits on a unit-cost RAM with word size w, and in particular consider the time-space trade-off (product of time and space in bits) for this problem. For comparison-based algorithms, the time-space ...
Comments