I/O Efficient Algorithms

[AV] The Input/Output Complexity of Sorting and Related Problems. A. Aggarwal and J. Vitter. CACM 31 (9), 1988.

[Alower] Lower bound on External Permuting/Sorting, Lecture notes by L. Arge.

[FJKT] Heaps and Heapsort on Secondary Storage. R.Fadel, K.V. Jakobsen, J. Katajainen, J. Teuhola. TCS 220 (2), 1999.

[AL] External partition element finding, Lecture notes by L. Arge and M. G. Lagoudakis.

[Z] I/O-Efficient Graph Algorithms. N. Zeh. Lecture notes.

[CGGTVV] External-Memory Graph Algorithms. Y-J. Chiang, M. T. Goodrich, E.F. Grove, R. Tamassia. D. E. Vengroff, and J. S. Vitter. Proc. SODA'95

[BGVW] On External Memory Graph Traversal. A.L. Buchsbaum, M. Goldwasser, S. Venkatasubramanian, J.R. Westbrook, Proc. SODA'00.

[MR] I/O-Complexity of Graph Algorithms. K. Munagala and A. Ranade. Proc. SODA'99.

[ABT] On External-Memory MST, SSSP and Multi-Way Planar Graph Separation. L. Arge, G. S. Brodal, and Laura Toma. Journal of Algorithms 53:186-206, 2004.

[KS] Improved Algorithms and Data Structures for Solving Graph Problems in External Memory. V. Kumar and E.J. Schwabe. Tech. report version of paper in SPDP'96.

[FLPR99] Cache-Oblivious Algorithms. M. Frigo, C. Leiserson, H. Prokop, and S. Ramachandran. Proc. FOCS '99.

[ABDHM] Cache-Oblivious Priority Queue and Graph Algorithm Applications. L. Arge, M. Bender, E. Demaine, B. Holland-Minkley and I. Munro. SICOMP, 36(6), 2007.

[BF02] Cache Oblivious Distribution Sweeping. G. S Brodal and R. Fagerberg. Proc. ICALP’02.

[IOBook] Ulrich Meyer, Peter Sanders, Jop Sibeyn (Eds.), Algorithms for Memory Hierarchies, Lecture Notes in Computer Science Vol 2625, Springer-Verlag Berlin Heidelberg, 2003.