Blocking for external graph searching

D. E. Knuth,The Art of Computer Programming, Vol. 3, Addison-Wesley, Reading, MA, 1973.

A. Aggarawal and J. Park, Notes on Searching in Multidimensional Monotone Arrays,Proceedings of the 29th Annual IEEE Symposium on Foundations of Computer Science, White Plains, NY, October 1988, pp. 497–512.

J. D. Ullman,Principles of Database and Knowledge-Base Systems, Computer Science Press, Rockville, MD, 1988.

A. Borodin, S. Irani, P. Raghavan, and B. Schieber, Competitive Paging with Locality of Reference,Proceedings of the 23rd ACM Symposium on Theory of Computing, New Orleans, LA, May 1991, pp. 249–259.

J. D. Ullman and M. Yannakakis, The Input/Output Complexity of Transitive Closure,Ann. Math. Artificial Intel. 3 (1991), 331–360.

A. L. Rosenberg, Preserving Proximity in Arrays,SIAM J. Comput. 4 (1975), 443–460.

R. A. DeMillo, S. C. Eisenstat, and R. J. Lipton, Preserving Average Proximity in Arrays,Comm. ACM 21 (1978), 228–231.

A. L. Rosenberg, Encoding Data Structures in Trees,J. Assoc. Comput. Mach. 26 (1979), 668–689.

A. L. Rosenberg, Data Encodings and Their Costs,Acta Inform. 9 (1978), 273–292.

A. L. Rosenberg and L. Snyder, Bounds on the Costs of Data Encodings,Math. Systems Theory 12 (1978), 9–39.

F. R. K. Chung, A. L. Rosenberg, and L. Snyder, Perfect Storage Representations for Families of Data Structures,SIAM J. Algebraic Discrete Methods 4 (1983), 548–565.

R. Aleliunas and A. L. Rosenberg, On Embedding Rectangular Grids in Square Grids,IEEE Trans. Comput. 31 (1982), 907–913.

R. J. Lipton, S. C. Eisenstat, and R. A. DeMillo, Space and Time Hierarchies for Classes of Control Structures and Data Structures,J. Assoc. Comput. Mach. 23 (1976), 720–732.

C. Berge,Graphs and Hypergraphs, 2nd edn., North-Holland, Amsterdam, 1976.

G. Reich and P. Widmayer, Beyond Steiner's Problem: A VSLI Oriented Generalization, inGraph-Theoretic Concepts in Computer Science: Proceedings of the 15th International Workshop WG '89 (G. Goos and J. Hartmanis, eds.), Lecture Notes in Computer Science, Vol. 411, Springer-Verlag, Berlin, 1990, pp. 196–210.

E. Ihler, Bounds on the Quality of Approximate Solutions to the Group Steiner Problem, inGraph-Theoretic Concepts in Computer Science, Proceedings of the 16th International Workshop WG '90 (G. Goos and J. Hartmanis, eds.), Lecture Notes in Computer Science, Vol. 484, Springer-Verlag, Berlin, 1991, pp. 109–118.

M. R. Garey and D. S. Johnson,Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, San Francisco, CA, 1979.