Amortized efficiency of list update rules

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Amortized efficiency of list update rules

Full text

Pdf (450 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the sixteenth annual ACM symposium on Theory of computing table of contents

Pages: 488 - 492

Year of Publication: 1984

ISBN:0-89791-133-4

Authors

Daniel Dominic Sleator
Robert Endre Tarjan

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 21, Downloads (12 Months): 56, Citation Count: 3

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/800057.808718 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	E. J. Anderson, P. Nash, and R. R. Weber, "A conterexample to a conjecture on optimal list ordering," J. Appl. Prob., to appear.
	2	L. A. Belady, "A study of replacement algorithms for vitrual storage computers," IBM Sys. J., 5 (1966), 78-101.
	3	J. L. Bentley and C. McGoech, "Worst-case analysis of self-organizing sequential search heuristics," Proc. 20th Allerton Conference on Communication, Control, and Computing, 1982.
	4	J. R. Bitner, "Heuristics that dynamically organize data structures," SIAM J. Computing, 8 (1979), 82-110.
	5	Edward G. Coffman, Jr. , Peter J. Denning, Operating Systems Theory, Prentice Hall Professional Technical Reference, 1973
	6	P. A. Franaszek , T. J. Wagner, Some Distribution-Free Aspects of Paging Algorithm Performance, Journal of the ACM (JACM), v.21 n.1, p.31-39, Jan. 1974 [doi>10.1145/321796.321800]
	7	Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
	8	Ronald Rivest, On self-organizing sequential search heuristics, Communications of the ACM, v.19 n.2, p.63-67, Feb. 1976 [doi>10.1145/359997.360000]
	9	Jeffrey R. Spirn, Program Behavior: Models and Measurements, Elsevier Science Inc., New York, NY, 1977

CITED BY 4

	Jon Louis Bentley , Daniel D. Sleator , Robert E. Tarjan , Victor K. Wei, A locally adaptive data compression scheme, Communications of the ACM, v.29 n.4, p.320-330, April 1986
	B. J. Oommen , D. C. Y. Ma, Deterministic Learning Automata Solutions to the Equipartitioning Problem, IEEE Transactions on Computers, v.37 n.1, p.2-13, January 1988
	Yangjun Chen , Donovan Cooke, On the transitive closure representation and adjustable compression, Proceedings of the 2006 ACM symposium on Applied computing, April 23-27, 2006, Dijon, France
	Fulvio Mastrogiovanni , Antonio Sgorbissa , Renato Zaccaria, Robust navigation in an unknown environment with minimal sensing and representation, IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics, v.39 n.1, p.212-229, February 2009