{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,12]],"date-time":"2025-02-12T23:10:13Z","timestamp":1739401813799,"version":"3.37.0"},"reference-count":40,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2009,10,27]],"date-time":"2009-10-27T00:00:00Z","timestamp":1256601600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2011,2]]},"DOI":"10.1007\/s00224-009-9242-2","type":"journal-article","created":{"date-parts":[[2009,10,26]],"date-time":"2009-10-26T15:14:08Z","timestamp":1256570048000},"page":"269-296","source":"Crossref","is-referenced-by-count":4,"title":["Optimal Cache-Oblivious Mesh Layouts"],"prefix":"10.1007","volume":"48","author":[{"given":"Michael A.","family":"Bender","sequence":"first","affiliation":[]},{"given":"Bradley C.","family":"Kuszmaul","sequence":"additional","affiliation":[]},{"given":"Shang-Hua","family":"Teng","sequence":"additional","affiliation":[]},{"given":"Kebin","family":"Wang","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2009,10,27]]},"reference":[{"key":"9242_CR1","doi-asserted-by":"crossref","unstructured":"Abello, J., Buchsbaum, A.L., Westbrook, J.: A functional approach to external graph algorithms. In: Proc. of the 6th Annual European Symposium on Algorithms (ESA), pp.\u00a0332\u2013343 (1998)","DOI":"10.1007\/3-540-68530-8_28"},{"issue":"9","key":"9242_CR2","doi-asserted-by":"crossref","first-page":"1116","DOI":"10.1145\/48529.48535","volume":"31","author":"A. Aggarwal","year":"1988","unstructured":"Aggarwal, A., Vitter, J.S.: The input\/output complexity of sorting and related problems. Commun. ACM 31(9), 1116\u20131127 (1988)","journal-title":"Commun. ACM"},{"key":"9242_CR3","first-page":"433","volume-title":"Proc. of the 7th Scandinavian Workshop on Algorithm Theory (SWAT)","author":"L. Arge","year":"2000","unstructured":"Arge, L., Brodal, G.S., Toma, L.: On external-memory MST, SSSP, and multi-way planar graph separation. In: Proc. of the 7th Scandinavian Workshop on Algorithm Theory (SWAT), pp. 433\u2013447. Springer, Berlin (2000)"},{"key":"9242_CR4","doi-asserted-by":"crossref","unstructured":"Arge, L., Meyer, U., Toma, L.: External memory algorithms for diameter and all-pair shortest-paths on sparse graphs. In: Proc. of 31st International Colloquium on Automata Languages and Programming (ICALP), pp.\u00a0146\u2013157 (2004)","DOI":"10.1007\/978-3-540-27836-8_15"},{"issue":"6","key":"9242_CR5","doi-asserted-by":"crossref","first-page":"1672","DOI":"10.1137\/S0097539703428324","volume":"36","author":"L. Arge","year":"2007","unstructured":"Arge, L., Bender, M.A., Demaine, E.D., Holland-Minkley, B., Munro, J.I.: An optimal cache-oblivious priority queue and its application to graph algorithms. SIAM J. Comput. 36(6), 1672\u20131695 (2007)","journal-title":"SIAM J. Comput."},{"key":"9242_CR6","doi-asserted-by":"crossref","unstructured":"Bender, M.A., Brodal, G.S., Fagerberg, R., Jacob, R., Vicari, E.: Optimal sparse matrix dense vector multiplication in the I\/O-model. In: Proceedings of the 19th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA), pp.\u00a061\u201370 (2007)","DOI":"10.1145\/1248377.1248391"},{"issue":"2","key":"9242_CR7","doi-asserted-by":"crossref","first-page":"300","DOI":"10.1016\/0022-0000(84)90071-0","volume":"28","author":"S.N. Bhatt","year":"1984","unstructured":"Bhatt, S.N., Leighton, F.T.: A framework for solving VLSI graph layout problems. J. Comput. Syst. Sci. 28(2), 300\u2013343 (1984)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"9242_CR8","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1006\/jpdc.1996.0107","volume":"37","author":"R.D. Blumofe","year":"1996","unstructured":"Blumofe, R.D., Joerg, C.F., Kuszmaul, B.C., Leiserson, C.E., Randall, K.H., Zhou, Y.: Cilk: an efficient multithreaded runtime system. J. Parallel Distrib. Comput. 37(1), 55\u201369 (1996)","journal-title":"J. Parallel Distrib. Comput."},{"key":"9242_CR9","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"426","DOI":"10.1007\/3-540-45465-9_37","volume-title":"Proc. of 29th International Colloquium on Automata Languages and Programming (ICALP)","author":"G.S. Brodal","year":"2002","unstructured":"Brodal, G.S., Fagerberg, R.: Cache oblivious distribution sweeping. In: Proc. of 29th International Colloquium on Automata Languages and Programming (ICALP). LNCS, vol.\u00a02380, pp.\u00a0426\u2013438. Springer, Berlin (2002)"},{"key":"9242_CR10","doi-asserted-by":"crossref","unstructured":"Brodal, G.S., Fagerberg, R., Meyer, U., Zeh, N.: Cache-oblivious data structures and algorithms for undirected breadth-first search and shortest paths. In: Proc. of the 9th Scandinavian Workshop on Algorithm Theory (SWAT), vol.\u00a03111, pp.\u00a0480\u2013492 (2004)","DOI":"10.1007\/978-3-540-27810-8_41"},{"key":"9242_CR11","first-page":"1","volume":"12","author":"G.S. Brodal","year":"2008","unstructured":"Brodal, G.S., Fagerberg, R., Vinther, K.: Engineering a cache-oblivious sorting algorithm. ACM J. Exp. Algorithmics 12, 1\u201323 (2008)","journal-title":"ACM J. Exp. Algorithmics"},{"key":"9242_CR12","unstructured":"Buchsbaum, A.L., Goldwasser, M., Venkatasubramanian, S., Westbrook, J.R.: On external memory graph traversal. In: Proc. of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp.\u00a0859\u2013860 (2000)"},{"key":"9242_CR13","unstructured":"Chiang, Y.-J., Goodrich, M.T., Grove, E.F., Tamassia, R., Vengroff, D.E., Vitter, J.S.: External-memory graph algorithms. In: Proc. of the 6th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp.\u00a0139\u2013149 (1995)"},{"key":"9242_CR14","unstructured":"Chowdhury, R.A., Ramachandran, V.: External-memory exact and approximate all-pairs shortest-paths in undirected graphs. In: Proc. of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp.\u00a0735\u2013744 (2005)"},{"issue":"2","key":"9242_CR15","doi-asserted-by":"crossref","first-page":"293","DOI":"10.1109\/JPROC.2004.840848","volume":"93","author":"J. Demmel","year":"2005","unstructured":"Demmel, J., Dongarra, J., Eijkhout, V., Fuentes, E., Antoine Petitet, R.V., Whaley, R.C., Yelick, K.: Self-adapting linear algebra algorithms and software. Proc. IEEE 93(2), 293\u2013312 (2005). Special Issue on Program Generation, Optimization, and Adaptation","journal-title":"Proc. IEEE"},{"key":"9242_CR16","first-page":"1381","volume-title":"Proceedings of the Acoustics, Speech, and Signal Processing","author":"M. Frigo","year":"1998","unstructured":"Frigo, M., Johnson, S.G.: F.F.T.W.: an adaptive software architecture for the FFT. In: Proceedings of the Acoustics, Speech, and Signal Processing, vol. 3, pp. 1381\u20131384. IEEE Press, New York (1998)"},{"key":"9242_CR17","doi-asserted-by":"crossref","unstructured":"Frigo, M., Leiserson, C.E., Prokop, H., Ramachandran, S.: Cache-oblivious algorithms. In: Proc. of the 40th IEEE Annual Symp. on Foundation of Computer Science (FOCS), pp.\u00a0285\u2013297 (1999)","DOI":"10.1109\/SFFCS.1999.814600"},{"issue":"1","key":"9242_CR18","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1137\/0606010","volume":"6","author":"C. Goldberg","year":"1985","unstructured":"Goldberg, C., West, D.: Bisection of circle colorings. SIAM J. Algebr. Discrete Methods 6(1), 93\u2013106 (1985)","journal-title":"SIAM J. Algebr. Discrete Methods"},{"issue":"2","key":"9242_CR19","doi-asserted-by":"crossref","first-page":"325","DOI":"10.1016\/0021-9991(87)90140-9","volume":"73","author":"L. Greengard","year":"1997","unstructured":"Greengard, L., Rokhlin, V.: A fast algorithm for particle simulations. J. Comput. Phys. 73(2), 325\u2013348 (1997)","journal-title":"J. Comput. Phys."},{"key":"9242_CR20","volume-title":"Computer Simulation Using Particles","author":"R.W. Hackney","year":"1981","unstructured":"Hackney, R.W., Eastwood, J.W.: Computer Simulation Using Particles. McGraw Hill, New York (1981)"},{"key":"9242_CR21","doi-asserted-by":"crossref","unstructured":"Hendrickson, B., Leland, R.: The Chaco user\u2019s guide\u2014version 2.0. Technical Report SAND94-2692, Sandia National Laboratories (1994)","DOI":"10.2172\/10106339"},{"issue":"1","key":"9242_CR22","doi-asserted-by":"crossref","first-page":"359","DOI":"10.1137\/S1064827595287997","volume":"20","author":"G. Karypis","year":"1998","unstructured":"Karypis, G., Kumar, V.: A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM J. Sci. Comput. 20(1), 359\u2013392 (1998)","journal-title":"SIAM J. Sci. Comput."},{"key":"9242_CR23","doi-asserted-by":"crossref","unstructured":"Kiwi, M., Spielman, D.A., Teng, S.-H.: Min-max-boundary domain decomposition. In: Theoretical Computer Science, vol.\u00a0261, pp.\u00a0253\u2013266 (2001)","DOI":"10.1016\/S0304-3975(00)00143-2"},{"key":"9242_CR24","doi-asserted-by":"crossref","unstructured":"Leighton, F.T.: A layout strategy for VLSI which is provably good. In: Proc. of the 14th Ann. ACM Symp. on Theory of Computing (STOC), pp.\u00a085\u201398 (1982)","DOI":"10.1145\/800070.802180"},{"key":"9242_CR25","first-page":"723","volume-title":"Proc. of the 10th Annual European Symposium on Algorithms (ESA)","author":"K. Mehlhorn","year":"2002","unstructured":"Mehlhorn, K., Meyer, U.: External-memory breadth-first search with sublinear I\/O. In: Proc. of the 10th Annual European Symposium on Algorithms (ESA), pp. 723\u2013735. Springer, Berlin (2002)"},{"key":"9242_CR26","unstructured":"Meyer, U.: External memory BFS on undirected graphs with bounded degree. In: Proc. of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp.\u00a087\u201388 (2001)"},{"key":"9242_CR27","doi-asserted-by":"crossref","first-page":"364","DOI":"10.1137\/S1064827594262613","volume":"19","author":"G.L. Miller","year":"1995","unstructured":"Miller, G.L., Teng, S.-H., Thurston, W., Vavasis, S.: Geometric separators for finite element meshes. SIAM J. Sci. Comput. 19, 364\u2013386 (1995)","journal-title":"SIAM J. Sci. Comput."},{"key":"9242_CR28","unstructured":"Munagala, K., Ranade, A.: I\/O-complexity of graph algorithms. In: Proc. of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp.\u00a0687\u2013694 (1999)"},{"issue":"2","key":"9242_CR29","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1007\/BF01940646","volume":"16","author":"M.H. Nodine","year":"1996","unstructured":"Nodine, M.H., Goodrich, M.T., Vitter, J.S.: Blocking for external graph searching. Algorithmica 16(2), 181\u2013214 (1996)","journal-title":"Algorithmica"},{"key":"9242_CR30","unstructured":"Prokop, H.: Cache-oblivious algorithms. Master\u2019s Thesis, MIT EECS, June 1999"},{"key":"9242_CR31","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1016\/0956-0521(91)90044-6","volume":"2","author":"H.D. Simon","year":"1991","unstructured":"Simon, H.D.: Partitioning of unstructured mesh problems for parallel processing. Comput. Syst. Eng. 2, 125\u2013148 (1991)","journal-title":"Comput. Syst. Eng."},{"issue":"2","key":"9242_CR32","doi-asserted-by":"crossref","first-page":"635","DOI":"10.1137\/S1064827595288942","volume":"19","author":"S.-H. Teng","year":"1998","unstructured":"Teng, S.-H.: Provably good partitioning and load balancing algorithms for parallel adaptive n-body simulation. SIAM J. Sci. Comput. 19(2), 635\u2013656 (1998)","journal-title":"SIAM J. Sci. Comput."},{"issue":"3","key":"9242_CR33","doi-asserted-by":"crossref","first-page":"227","DOI":"10.1142\/S0218195900000152","volume":"10","author":"S.-H. Teng","year":"2000","unstructured":"Teng, S.-H., Wong, C.W.: Unstructured mesh generation: theory, practice, and perspectives. Int. J. Comput. Geom. Appl. 10(3), 227\u2013266 (2000)","journal-title":"Int. J. Comput. Geom. Appl."},{"key":"9242_CR34","unstructured":"Toledo, S.A.: Quantitative performance modeling of scientific computations and creating locality in numerical algorithms. Ph.D. Thesis (1995). Supervisor: Charles E. Leiserson"},{"issue":"4","key":"9242_CR35","doi-asserted-by":"crossref","first-page":"1065","DOI":"10.1137\/S0895479896297744","volume":"18","author":"S.A. Toledo","year":"1997","unstructured":"Toledo, S.A.: Locality of reference in LU decomposition with partial pivoting. SIAM J. Matrix Anal. Appl. 18(4), 1065\u20131081 (1997)","journal-title":"SIAM J. Matrix Anal. Appl."},{"key":"9242_CR36","unstructured":"Vudac, R., Demmel, J.W., Yelick, K.A.: The optimized sparse kernel interface (OSKI) library: user\u2019s guide for version 1.0.1b. Berkeley Benchmarking and OPtimizationBeBOP) Group, 15 March 2006"},{"key":"9242_CR37","unstructured":"Vuduc, R.W.: Automatic performance tuning of sparse matrix kernels. Ph.D. Thesis, University of California, Berkeley (2003)"},{"key":"9242_CR38","doi-asserted-by":"crossref","unstructured":"Weikum, G., Moenkeberg, A., Hasse, C., Zabback, P.: Self-tuning database technology and information services: from wishful thinking to viable engineering. In: Proceedings of International Conference on Very Large Data Bases (VLDB), pp.\u00a020\u201331 (2002)","DOI":"10.1016\/B978-155860869-6\/50011-1"},{"key":"9242_CR39","doi-asserted-by":"crossref","unstructured":"Whaley, R.C., Dongarra, J.: Automatically tuned linear algebra software. In: SuperComputing, pp.\u00a01\u201327 (1998)","DOI":"10.1109\/SC.1998.10004"},{"key":"9242_CR40","doi-asserted-by":"crossref","unstructured":"Yoon, S.-E., Lindstrom, P., Pascucci, V., Manocha, D.: Cache-oblivious mesh layouts. In: ACM SIGGRAPH and Transactions on Graphics, pp.\u00a0886\u2013893 (2005)","DOI":"10.1145\/1073204.1073278"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-009-9242-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-009-9242-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-009-9242-2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,12]],"date-time":"2025-02-12T22:44:50Z","timestamp":1739400290000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-009-9242-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,10,27]]},"references-count":40,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2011,2]]}},"alternative-id":["9242"],"URL":"https:\/\/doi.org\/10.1007\/s00224-009-9242-2","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"type":"print","value":"1432-4350"},{"type":"electronic","value":"1433-0490"}],"subject":[],"published":{"date-parts":[[2009,10,27]]}}}