Improved Bounds on the Problem of Time-Space Trade-Off in the Pebble Game

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback
Take a look at the new version of this page: [ beta version ]. Tell us what you think.

Improved Bounds on the Problem of Time-Space Trade-Off in the Pebble Game

Full text

Pdf (484 KB)

Source

Journal of the ACM (JACM) archive
Volume 27 , Issue 4 (October 1980) table of contents

Pages: 839 - 849

Year of Publication: 1980

ISSN:0004-5411

Author

Rudiger Reischuk

Fakultat für Mathematik, Universitat Bielefeld, 4800 Bielefeld 1, Federal Republic of Germany

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 2, Downloads (12 Months): 22, Citation Count: 2

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/322217.322233 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Stephen A. Cook, An observation on time-storage trade off, Proceedings of the fifth annual ACM symposium on Theory of computing, p.29-33, April 30-May 02, 1973, Austin, Texas, United States [doi>10.1145/800125.804032]
	2	John Hopcroft , Wolfgang Paul , Leslie Valiant, On Time Versus Space, Journal of the ACM (JACM), v.24 n.2, p.332-337, April 1977 [doi>10.1145/322003.322015]
	3	Wolfgang J. Paul , Robert Endre Tarjan, Time-Space Trade-Offs in a Pebble Game, Proceedings of the Fourth Colloquium on Automata, Languages and Programming, p.365-369, July 18-22, 1977
	4	PAUL, W j, TAR JAN, R.E, AND CELONI, J R Space bounds for a game on graphs Math. Syst Theory 10 (1977), 239-251
	5	Nicholas Pippenger, A Time-Space Trade-Off, Journal of the ACM (JACM), v.25 n.3, p.509-515, July 1978 [doi>10.1145/322077.322091]
	6	SAVAGE, J.E., AND SWAMY, S Space-time trade-offs on the FFT algorithm. IEEE Trans. Inf. Theory 24, (1978), 563-568.
	7	Martin Tompa, Time-space tradeoffs for computing functions, using connectivity properties of their circuits, Proceedings of the tenth annual ACM symposium on Theory of computing, p.196-204, May 01-03, 1978, San Diego, California, United States [doi>10.1145/800133.804348]

CITED BY 2

	Thomas Lengauer , Robert E. Tarjan, Asymptotically tight bounds on time-space trade-offs in a pebble game, Journal of the ACM (JACM), v.29 n.4, p.1087-1130, Oct. 1982
	Joseph Ja'Ja', Time-Space trade-offs for some algebraic problems, Journal of the ACM (JACM), v.30 n.3, p.657-667, July 1983