{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,5]],"date-time":"2026-05-05T07:22:10Z","timestamp":1777965730143,"version":"3.51.4"},"publisher-location":"Cham","reference-count":25,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783031099922","type":"print"},{"value":"9783031099939","type":"electronic"}],"license":[{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2022]]},"DOI":"10.1007\/978-3-031-09993-9_8","type":"book-chapter","created":{"date-parts":[[2022,6,24]],"date-time":"2022-06-24T20:12:42Z","timestamp":1656101562000},"page":"135-153","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["The Red-Blue Pebble Game on\u00a0Trees and\u00a0DAGs with\u00a0Large Input"],"prefix":"10.1007","author":[{"given":"Niels","family":"Gleinig","sequence":"first","affiliation":[]},{"given":"Torsten","family":"Hoefler","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,6,25]]},"reference":[{"key":"8_CR1","doi-asserted-by":"crossref","unstructured":"Aggarwal, A., Vitter, J.S.: The input\/output complexity of sorting and related problems. Commun. ACM 31(9), 1116\u20131127 (1988)","DOI":"10.1145\/48529.48535"},{"key":"8_CR2","doi-asserted-by":"crossref","unstructured":"Arge, L., Toma, L., Zeh, N.: I\/o-efficient topological sorting of planar DAGs. In: Proceedings of the Fifteenth Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA 2003, pp. 85\u201393, New York, NY, USA. ACM (2003)","DOI":"10.1145\/777412.777427"},{"key":"8_CR3","doi-asserted-by":"crossref","unstructured":"Austrin, P., Pitassi, T., Wu, Y.: Inapproximability of treewidth, one-shot pebbling, and related layout problems. CoRR, abs\/1109.4910 (2011)","DOI":"10.1007\/978-3-642-32512-0_2"},{"key":"8_CR4","doi-asserted-by":"crossref","unstructured":"Ballard, G., Demmel, J., Holtz, O., Schwartz, O.: Communication-optimal parallel and sequential cholesky decomposition. CoRR, abs\/0902.2537 (2009)","DOI":"10.1145\/1583991.1584054"},{"key":"8_CR5","doi-asserted-by":"crossref","unstructured":"Bender, M.A., et al.: The i\/o complexity of computing prime tables, pp. 192\u2013206 (2016)","DOI":"10.1007\/978-3-662-49529-2_15"},{"key":"8_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1007\/3-540-40064-8_6","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"G Bilardi","year":"2000","unstructured":"Bilardi, G., Pietracaprina, A., D\u2019Alberto, P.: On the space and access complexity of computation DAGs. In: Brandes, U., Wagner, D. (eds.) WG 2000. LNCS, vol. 1928, pp. 47\u201358. Springer, Heidelberg (2000). https:\/\/doi.org\/10.1007\/3-540-40064-8_6"},{"key":"8_CR7","doi-asserted-by":"crossref","unstructured":"Carpenter, T., Rastello, F., Sadayappan, P., Sidiropoulos, A.: Brief announcement: approximating the i\/o complexity of one-shot red-blue pebbling. In: Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2016, pp. 161\u2013163, New York, NY, USA. ACM (2016)","DOI":"10.1145\/2935764.2935807"},{"key":"8_CR8","doi-asserted-by":"crossref","unstructured":"Chan, S.M.: Pebble Games and Complexity. PhD thesis, EECS Department, University of California, Berkeley, August 2013","DOI":"10.1109\/CCC.2013.22"},{"key":"8_CR9","doi-asserted-by":"crossref","unstructured":"Chan, S.M., Lauria, M., Nordstr\u00f6m, J., Vinyals, M.: Hardness of approximation in PSPACE and separation results for pebble games, pp. 466\u2013485 (2015)","DOI":"10.1109\/FOCS.2015.36"},{"key":"8_CR10","unstructured":"Chiang, Y.-J., Goodrich, M., Grove, E., Tamassia, R., Vengroff, D., Vitter, J.: External-memory graph algorithms, May 1995"},{"key":"8_CR11","doi-asserted-by":"crossref","unstructured":"Demaine, E.D., Liu, Q.C.: Inapproximability of the standard pebble game and hard to pebble graphs, pp. 313\u2013324 (2017)","DOI":"10.1007\/978-3-319-62127-2_27"},{"key":"8_CR12","doi-asserted-by":"crossref","unstructured":"Demaine, E.D., Liu, Q.C.: Red-blue pebble game: complexity of computing the trade-off between cache size and memory transfers. In: Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures, SPAA 2018, pp. 195\u2013204, New York, NY, USA. ACM (2018)","DOI":"10.1145\/3210377.3210387"},{"issue":"1","key":"8_CR13","doi-asserted-by":"publisher","first-page":"206","DOI":"10.1137\/080731992","volume":"34","author":"J Demmel","year":"2012","unstructured":"Demmel, J., Grigori, L., Hoemmen, M., Langou, J.: Communication-optimal parallel and sequential QR and LU factorizations. SIAM J. Sci. Comput. 34(1), 206\u2013239 (2012)","journal-title":"SIAM J. Sci. Comput."},{"key":"8_CR14","doi-asserted-by":"crossref","unstructured":"Driscoll, M., Georganas, E., Koanantakool, P., Solomonik, E., Yelick, K.: A communication-optimal n-body algorithm for direct interactions. In: 2013 IEEE 27th International Symposium on Parallel and Distributed Processing, pp. 1075\u20131084 (2013)","DOI":"10.1109\/IPDPS.2013.108"},{"key":"8_CR15","doi-asserted-by":"crossref","unstructured":"Elango, V., Rastello, F., Pouchet, L.-N., Ramanujam, J., Sadayappan, P.: On characterizing the data movement complexity of computational DAGs for parallel execution. CoRR, abs\/1404.4767 (2014)","DOI":"10.1145\/2612669.2612694"},{"key":"8_CR16","doi-asserted-by":"crossref","unstructured":"Gilbert, J.R., Lengauer, T., Tarjan, R.E.: The pebbling problem is complete in polynomial space, pp. 237\u2013248 (1979)","DOI":"10.1145\/800135.804418"},{"key":"8_CR17","doi-asserted-by":"crossref","unstructured":"Jia-Wei, H., Kung, H.T.: I\/o complexity: the red-blue pebble game, pp. 326\u2013333 (1981)","DOI":"10.1145\/800076.802486"},{"key":"8_CR18","doi-asserted-by":"crossref","unstructured":"Kwasniewski, G., Kabi\u0107, M., Besta, M., VandeVondele, J., Solc\u00e0, R., Hoefler, T.: Red-blue pebbling revisited: near optimal parallel matrix-matrix multiplication. In: Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, SC 2019, New York, NY, USA (2019). Association for Computing Machinery","DOI":"10.1145\/3295500.3356181"},{"key":"8_CR19","doi-asserted-by":"crossref","unstructured":"Liu, J.W.H.: On the storage requirement in the out-of-core multifrontal method for sparse factorization. ACM Trans. Math. Softw. 12(3), 249\u2013264 (1986)","DOI":"10.1145\/7921.11325"},{"key":"8_CR20","unstructured":"Liu, Q.: Red-blue and standard pebble games : complexity and applications in the sequential and parallel models. Master\u2019s thesis, Department of Electrical Engineering and Computer Science, MIT, Massachusetts (2018)"},{"key":"8_CR21","doi-asserted-by":"crossref","unstructured":"Maheshwari, A., Zeh, N.: A survey of techniques for designing i\/o-efficient algorithms, pp. 36\u201361, January 2002","DOI":"10.1007\/3-540-36574-5_3"},{"key":"8_CR22","doi-asserted-by":"crossref","unstructured":"Marchal, L., McCauley, S., Simon, B., Vivien, F.: Minimizing I\/Os in out-of-core task tree scheduling. In: 2017 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW), pp. 884\u2013893 (2017)","DOI":"10.1109\/IPDPSW.2017.58"},{"key":"8_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"434","DOI":"10.1007\/978-3-540-39658-1_40","volume-title":"Algorithms - ESA 2003","author":"U Meyer","year":"2003","unstructured":"Meyer, U., Zeh, N.: I\/O-efficient undirected shortest paths. In: Di Battista, G., Zwick, U. (eds.) ESA 2003. LNCS, vol. 2832, pp. 434\u2013445. Springer, Heidelberg (2003). https:\/\/doi.org\/10.1007\/978-3-540-39658-1_40"},{"key":"8_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1007\/978-3-642-19222-7_12","volume-title":"Combinatorial Algorithms","author":"D Ranjan","year":"2011","unstructured":"Ranjan, D., Savage, J., Zubair, M.: Upper and lower I\/O bounds for pebbling r-Pyramids. In: Iliopoulos, C.S., Smyth, W.F. (eds.) IWOCA 2010. LNCS, vol. 6460, pp. 107\u2013120. Springer, Heidelberg (2011). https:\/\/doi.org\/10.1007\/978-3-642-19222-7_12"},{"key":"8_CR25","doi-asserted-by":"crossref","unstructured":"Unat, D., et al.: Trends in Data Locality Abstractions for HPC Systems. IEEE Trans. Parallel Distrib. Syst. (TPDS) 28(10), 3007\u20133020 (2017)","DOI":"10.1109\/TPDS.2017.2703149"}],"container-title":["Lecture Notes in Computer Science","Structural Information and Communication Complexity"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-09993-9_8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,6,24]],"date-time":"2022-06-24T20:13:29Z","timestamp":1656101609000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-09993-9_8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022]]},"ISBN":["9783031099922","9783031099939"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-09993-9_8","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022]]},"assertion":[{"value":"25 June 2022","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"SIROCCO","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Colloquium on Structural Information and Communication Complexity","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Paderborn","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Germany","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2022","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"27 June 2022","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"29 June 2022","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"29","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"sirocco2022","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/sirocco2022.cs.uni-paderborn.de\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}