Bounds on the costs of data encodings. (English) Zbl 0403.68018


68P05 Data structures
Full Text: DOI


[1] R. A. DeMillo, S. C. Eisenstat, and R. J. Lipton, Preserving average proximity in arrays,C. ACM, 21, 228–231. · Zbl 0378.68014
[2] C. C. Gotlieb and F. W. Tompa, Choosing a storage schema,Acta Inform. 3, 297–319 (1974). · Zbl 0302.68051
[3] G. H. Hardy, J. E. Littlewood, and G. Polya,Inequalities, Cambridge Univ. Press, 1967.
[4] L. H. Harper, Optimal assignments of numbers to vertices,J. Soc. Indust. Appl. Math., 12, 131–135 (1964). · Zbl 0222.94004
[5] L. H. Harper, Optimal numberings and isoperimetric problems on graphs,J. Comb. Th., 1, 385–393 (1966). · Zbl 0158.20802
[6] M. A. Iordansk’ii, Minimalnye numeratsii vershin derevyev (in Russian),Problemy Kibernetiki, 31, 109–132 (1976).
[7] D. E. Knuth,The Art of Computer Programming I: Fundamental Algorithms, Addison-Wesley, Reading, MA, 1968. · Zbl 0191.17903
[8] R. J. Lipton, S. C. Eisenstat, and R. A. DeMillo, Space and time hierarchies for classes of control structures and data structures,J. ACM, 23, 720–732 (1976). · Zbl 0333.68024
[9] J. L. Pfaltz, Representing graphs by Knuth trees,J. ACM, 22, 361–366 (1975). · Zbl 0305.68033
[10] A. L. Rosenberg, Preserving proximity in arrays,SIAM J. Comput., 4, 443–460 (1975). · Zbl 0324.68016
[11] A. L. Rosenberg, Data encodings and their costs,Acta Inform, 9, 273–292 (1978). · Zbl 0434.68048
[12] A. L. Rosenberg, Encoding data structures in trees, IBM RC-6793, 1977; submitted for publication.
[13] P. Scheuermann and J. Heller, A view of logical data organization and its mapping to physical storage,Proc. 3rd Texas Conf. on Computing Systems, 1974.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.