Data encodings and their costs. (English) Zbl 0434.68048


68R10 Graph theory (including graph drawing) in computer science
68Q25 Analysis of algorithms and problem complexity
68P05 Data structures
Full Text: DOI


[1] Cook, S.A.: The complexity of theorem-proving procedures. Proc. 3rd ACM Symp. on Theory of Computing, 1970, pp. 151-158
[2] DeMillo, R.A., Eisenstat, S.C., Lipton, R.E.: Preserving average proximity in arrays. Comm. ACM (to appear) · Zbl 0378.68014
[3] Fischer, P.C., Meyer, A.R., Rosenberg, A.L.: Real-time simulation of multihead tape units. J. Assoc. Comput. Mach. 19, 590-607 (1972) · Zbl 0261.68027
[4] Garey, M.R., Graham, R.L., Johnson, D.S., Knuth, D.E.: Complexity results for bandwidth minimization. Unpublished typescript, 1977 · Zbl 0385.05048
[5] Garey, M.R., Johnson, D.S., Stockmeyer, L.J.: Some simplified NP-complete graph problems. Theoret. Comput. Sci. 1, 237-267 (1976) · Zbl 0338.05120
[6] Gotlieb, C.C., Tompa, F.W.: Choosing a storage schema. Acta Informat. 3, 297-319 (1974) · Zbl 0302.68051
[7] Hardy, G.H., Littlewood, J.E., Pólya, G.: Inequalities. Cambridge Univ. Press 1967
[8] Harper, L.H.: Optimal assignments of numbers to vertices. J. Soc. Indust. Appl. Math. 12, 131-135 (1964) · Zbl 0222.94004
[9] Harper, L.H.: Optimal numberings and isoperimetric problems. J. Combinatorial Theory 1, 385-393 (1966) · Zbl 0158.20802
[10] Hennie, F.C.: One-tape, off-line Turing machine computations. Information and Control 8, 553-578 (1965) · Zbl 0231.02048
[11] Iordansk’ii, M.A.: Minimalnye numeratsii vershin derevyev [in Russian]. Problemy Kibernet. 31, 109-132 (1976)
[12] Knuth, D.E.: The art of computer programming. I. Fundamental algorithms. Reading, MA: Addison-Wesley 1968 · Zbl 0191.17903
[13] Knuth, D.E.: The art of computer programming. III. Sorting and searching. Reading, MA: Addison-Wesley 1973 · Zbl 0302.68010
[14] Lipton, R.E., Eisenstat, S.C., DeMillo, R.A.: Space and time hierarchies for classes of control structures and data structures. J. Assoc. Comput. Mach. 23, 720-732 (1976) · Zbl 0333.68024
[15] Papadimitriou, Ch. H.: The NP-completeness of the bandwidth minimization problem. Computing 16, 263-270 (1976) · Zbl 0321.65019
[16] Pippenger, N., Fischer, M.J.: Relations among complexity measures. IBM Report RC-6569, 1977 · Zbl 0405.68041
[17] Pfaltz, J.L.: Representing graphs by Knuth trees. J. Assoc. Comput. Mach. 22, 361-366 (1975) · Zbl 0305.68033
[18] Rosenberg, A.L.: Preserving proximity in arrays. SIAM J. Comput. 4, 443-460 (1975) · Zbl 0324.68016
[19] Rosenberg, A.L.: Storage mappings for extendible arrays. IBM Report RC-5798, 1976. In: Current trends in programming methodology. IV. Data structuring (R.T. Yeh, ed.). Englewood Cliffs, NJ: Prentice-Hall (to appear)
[20] Rosenberg, A.L., Snyder, L.: Bounds on the costs of data encodings. Math. Systems theory (to appear) · Zbl 0403.68018
[21] Scheuermann, P., Heller, J.: A view of logical data organization and its mapping to physical storage. Proc. 3rd Texas Conf. on Computing Systems, 1974
[22] Sekanina, M.: On an ordering of the set of vertices of a connected graph. Publ. Fac. Sci. Univ. Brno, No. 412, 137-142 (1960) · Zbl 0118.18903
[23] Sheidvasser, M.A.: O dline i shirine razmeshchenii grafov v reshetkakh [in Russian]. Problemy Kibernet. 29, 63-102 (1974)
[24] Shneiderman, B., Shapiro, S.C.: Toward a theory of encoded data structures and data translation. Internat. J. Comput. Information Sci. 5, 33-43 (1976) · Zbl 0317.68035
[25] Standish, T.A.: Data structures ? an axiomatic approach. In: Current trends in programming methodology. IV. Data structuring (R.T. Yeh, ed.). Englewood Cliffs, NJ: Prentice-Hall (to appear)
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.