{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,20]],"date-time":"2025-12-20T22:24:53Z","timestamp":1766269493566},"publisher-location":"Cham","reference-count":21,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319079585"},{"type":"electronic","value":"9783319079592"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-319-07959-2_11","type":"book-chapter","created":{"date-parts":[[2014,6,10]],"date-time":"2014-06-10T12:44:25Z","timestamp":1402404265000},"page":"123-137","source":"Crossref","is-referenced-by-count":6,"title":["Beyond Synchronous: New Techniques for External-Memory Graph Connectivity and Minimum Spanning Forest"],"prefix":"10.1007","author":[{"given":"Aapo","family":"Kyrola","sequence":"first","affiliation":[]},{"given":"Julian","family":"Shun","sequence":"additional","affiliation":[]},{"given":"Guy","family":"Blelloch","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"3","key":"11_CR1","doi-asserted-by":"publisher","first-page":"437","DOI":"10.1007\/s00453-001-0088-5","volume":"32","author":"J. Abello","year":"2002","unstructured":"Abello, J., Buchsbaum, A.L., Westbrook, J.R.: A functional approach to external graph algorithms. Algorithmica\u00a032(3), 437\u2013458 (2002)","journal-title":"Algorithmica"},{"issue":"9","key":"11_CR2","doi-asserted-by":"publisher","first-page":"1116","DOI":"10.1145\/48529.48535","volume":"31","author":"A. Aggarwal","year":"1988","unstructured":"Aggarwal, A., Vitter, J., et al.: The input\/output complexity of sorting and related problems. Commun. ACM\u00a031(9), 1116\u20131127 (1988)","journal-title":"Commun. ACM"},{"issue":"2","key":"11_CR3","doi-asserted-by":"publisher","first-page":"186","DOI":"10.1016\/j.jalgor.2004.04.001","volume":"53","author":"L. Arge","year":"2004","unstructured":"Arge, L., Brodal, G.S., Toma, L.: On external-memory MST, SSSP and multi-way planar graph separation. J. Algorithms\u00a053(2), 186\u2013206 (2004)","journal-title":"J. Algorithms"},{"key":"11_CR4","doi-asserted-by":"publisher","first-page":"44","DOI":"10.1145\/1150402.1150412","volume-title":"12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining","author":"L. Backstrom","year":"2006","unstructured":"Backstrom, L., Huttenlocher, D., Kleinberg, J., Lan, X.: Group formation in large social networks: Membership, growth, and evolution. In: 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 44\u201354. ACM, New York (2006)"},{"key":"11_CR5","volume-title":"Parallel and Distributed Computation: Numerical Methods","author":"D.P. Bertsekas","year":"1989","unstructured":"Bertsekas, D.P., Tsitsiklis, J.N.: Parallel and Distributed Computation: Numerical Methods. Prentice-Hall, Upper Saddle River (1989)"},{"issue":"2","key":"11_CR6","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1145\/1480506.1480511","volume":"42","author":"P. Boldi","year":"2008","unstructured":"Boldi, P., Santini, M., Vigna, S.: A large time-aware web graph. ACM SIGIR Forum\u00a042(2), 33\u201338 (2008)","journal-title":"ACM SIGIR Forum"},{"key":"11_CR7","unstructured":"Boruvka, O.: O jistem problemu minimalnim (about a certain minimal problem). In: Prace, Moravske Prirodovedecke Spolecnosti, pp. 37\u201358 (1926)"},{"key":"11_CR8","first-page":"139","volume-title":"6th Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Y.J. Chiang","year":"1995","unstructured":"Chiang, Y.J., Goodrich, M.T., Grove, E.F., Tamassia, R., Vengroff, D.E., Vitter, J.S.: External-memory graph algorithms. In: 6th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 139\u2013149. SIAM, Philadelphia (1995)"},{"key":"11_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"640","DOI":"10.1007\/11561071_57","volume-title":"Algorithms \u2013 ESA 2005","author":"R. Dementiev","year":"2005","unstructured":"Dementiev, R., Kettner, L., Sanders, P.: STXXL: Standard template library for XXL data sets. In: Brodal, G.S., Leonardi, S. (eds.) ESA 2005. LNCS, vol.\u00a03669, pp. 640\u2013651. Springer, Heidelberg (2005)"},{"key":"11_CR10","series-title":"IFIP","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1007\/1-4020-8141-3_17","volume-title":"Exploring New Frontiers of Theoretical Informatics","author":"R. Dementiev","year":"2004","unstructured":"Dementiev, R., Sanders, P., Schultes, D., Sibeyn, J.: Engineering an external memory minimum spanning tree algorithm. In: Levy, J.-J., Mayr, E.W., Mitchell, J.C. (eds.) Exploring New Frontiers of Theoretical Informatics. IFIP, vol.\u00a0155, pp. 195\u2013208. Springer, Heidelberg (2004)"},{"key":"11_CR11","unstructured":"Gonzalez, J., Low, Y., Guestrin, C.: Residual splash for optimally parallelizing belief propagation. In: International Conference on Artificial Intelligence and Statistics. pp. 177\u2013184. JMLR (2009)"},{"key":"11_CR12","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1145\/2487575.2487581","volume-title":"19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining","author":"W.S. Han","year":"2013","unstructured":"Han, W.S., Lee, S., Park, K., Lee, J.H., Kim, M.S., Kim, J., Yu, H.: TurboGraph: A fast parallel graph engine handling billion-scale graphs in a single PC. In: 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 77\u201385. ACM, New York (2013)"},{"key":"11_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"62","DOI":"10.1007\/3-540-36574-5_4","volume-title":"Algorithms for Memory Hierarchies","author":"I. Katriel","year":"2003","unstructured":"Katriel, I., Meyer, U.: Elementary graph algorithms in external memory. In: Meyer, U., Sanders, P., Sibeyn, J. (eds.) Algorithms for Memory Hierarchies. LNCS, vol.\u00a02625, pp. 62\u201384. Springer, Heidelberg (2003)"},{"key":"11_CR14","first-page":"169","volume-title":"8th IEEE Symposium on Parallel and Distributed Processing","author":"V. Kumar","year":"1996","unstructured":"Kumar, V., Schwabe, E.J.: Improved algorithms and data structures for solving graph problems in external memory. In: 8th IEEE Symposium on Parallel and Distributed Processing, pp. 169\u2013176. IEEE Press, New York (1996)"},{"key":"11_CR15","doi-asserted-by":"publisher","first-page":"591","DOI":"10.1145\/1772690.1772751","volume-title":"19th International Conference on World Wide Web","author":"H. Kwak","year":"2010","unstructured":"Kwak, H., Lee, C., Park, H., Moon, S.: What is Twitter, a social network or a news media? In: 19th International Conference on World Wide Web, pp. 591\u2013600. ACM, New York (2010)"},{"key":"11_CR16","unstructured":"Kyrola, A., Blelloch, G., Guestrin, C.: GraphChi: Large-scale graph computation on just a PC. In: 10th USENIX Symposium on Operating Systems Design and Implementation, vol.\u00a08, pp. 31\u201346. USENIX (2012)"},{"key":"11_CR17","unstructured":"Lambert, O., Sibeyn, J.F., Stadtwald, I.: Parallel and external list ranking and connected components. In: International Conference of Parallel and Distributed Computing and Systems, pp. 454\u2013460. IASTED (1999)"},{"issue":"1","key":"11_CR18","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1080\/15427951.2009.10129177","volume":"6","author":"J. Leskovec","year":"2009","unstructured":"Leskovec, J., Lang, K.J., Dasgupta, A., Mahoney, M.W.: Community structure in large networks: Natural cluster sizes and the absence of large well-defined clusters. Internet Mathematics\u00a06(1), 29\u2013123 (2009)","journal-title":"Internet Mathematics"},{"key":"11_CR19","volume-title":"Synthesis of Parallel Algorithms","author":"J.H. Reif","year":"1993","unstructured":"Reif, J.H.: Synthesis of Parallel Algorithms. Morgan Kaufmann, San Francisco (1993)"},{"key":"11_CR20","first-page":"472","volume-title":"24th ACM Symposium on Operating Systems Principles","author":"A. Roy","year":"2013","unstructured":"Roy, A., Mihailovic, I., Zwaenepoel, W.: X-Stream: edge-centric graph processing using streaming partitions. In: 24th ACM Symposium on Operating Systems Principles, pp. 472\u2013488. ACM, New York (2013)"},{"key":"11_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"468","DOI":"10.1007\/978-3-540-27810-8_40","volume-title":"Algorithm Theory - SWAT 2004","author":"J.F. Sibeyn","year":"2004","unstructured":"Sibeyn, J.F.: External connected components. In: Hagerup, T., Katajainen, J. (eds.) SWAT 2004. LNCS, vol.\u00a03111, pp. 468\u2013479. Springer, Heidelberg (2004)"}],"container-title":["Lecture Notes in Computer Science","Experimental Algorithms"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-07959-2_11","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2018,10,5]],"date-time":"2018-10-05T22:43:52Z","timestamp":1538779432000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-07959-2_11"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783319079585","9783319079592"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-07959-2_11","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]}}}