{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T14:39:25Z","timestamp":1742999965675,"version":"3.40.3"},"publisher-location":"Singapore","reference-count":17,"publisher":"Springer Nature Singapore","isbn-type":[{"type":"print","value":"9789819610921"},{"type":"electronic","value":"9789819610938"}],"license":[{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2025]]},"DOI":"10.1007\/978-981-96-1093-8_17","type":"book-chapter","created":{"date-parts":[[2025,2,20]],"date-time":"2025-02-20T11:46:50Z","timestamp":1740052010000},"page":"202-213","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Efficient Partitioning Algorithms for\u00a0Optimizing Big Graph Computation"],"prefix":"10.1007","author":[{"given":"Baoling","family":"Ning","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yupeng","family":"Gao","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,2,20]]},"reference":[{"issue":"6","key":"17_CR1","doi-asserted-by":"publisher","first-page":"929","DOI":"10.1007\/s00224-006-1350-7","volume":"39","author":"K Andreev","year":"2006","unstructured":"Andreev, K., R\u00e4cke, H.: Balanced graph partitioning. Theory Comput. Syst. 39(6), 929\u2013939 (2006)","journal-title":"Theory Comput. Syst."},{"key":"17_CR2","doi-asserted-by":"crossref","unstructured":"Arora, S., Rao, S., et al.: Expander flows, geometric embeddings and graph partitioning. In: STOC 2004, pp. 222\u2013231 (2004)","DOI":"10.1145\/1007352.1007355"},{"key":"17_CR3","doi-asserted-by":"crossref","unstructured":"Chlamtac, E., Makarychev, K., et al.: How to play unique games using embeddings. In FOCS 2006, pp. 687\u2013696 (2006)","DOI":"10.1109\/FOCS.2006.36"},{"key":"17_CR4","volume-title":"Design and Analysis of Approximation Algorithms","author":"D Dingzhu","year":"2011","unstructured":"Dingzhu, D., Ge, K., et al.: Design and Analysis of Approximation Algorithms. Springer, New York (2011)"},{"issue":"6","key":"17_CR5","doi-asserted-by":"publisher","first-page":"2187","DOI":"10.1137\/S0097539796308217","volume":"28","author":"G Even","year":"1999","unstructured":"Even, G., Naor, J., et al.: Fast approximate graph partitioning algorithms. SIAM J. Comput. 28(6), 2187\u20132214 (1999)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"17_CR6","doi-asserted-by":"publisher","first-page":"585","DOI":"10.1145\/347476.347478","volume":"47","author":"G Even","year":"2000","unstructured":"Even, G., Naor, J., et al.: Divide-and-conquer approximation algorithms via spreading metrics. J. ACM 47(4), 585\u2013616 (2000)","journal-title":"J. ACM"},{"key":"17_CR7","doi-asserted-by":"crossref","unstructured":"Fan, W., Jin, R., et al.: Application driven graph partitioning. In: SIGMOD 2020, pp. 1765\u20131779 (2020)","DOI":"10.1145\/3318464.3389745"},{"issue":"2","key":"17_CR8","doi-asserted-by":"publisher","first-page":"354","DOI":"10.1007\/s00453-013-9802-3","volume":"71","author":"Andreas Emil Feldmann and Luca Foschini","year":"2015","unstructured":"Andreas Emil Feldmann and Luca Foschini: Balanced partitions of trees and applications. Algorithmica 71(2), 354\u2013376 (2015)","journal-title":"Algorithmica"},{"key":"17_CR9","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, New York, USA, 1979"},{"key":"17_CR10","doi-asserted-by":"crossref","unstructured":"Garey, M.R., Johnson, D.S., et al.: Some simplified npcomplete graph problems. Theor. Comput. Sci. 1(3), 237\u2013267 (1976)","DOI":"10.1016\/0304-3975(76)90059-1"},{"key":"17_CR11","unstructured":"Gonzalez, J.E., Low, Y., et al.: Powergraph: distributed graph-parallel computation on natural graphs. In: OSDI 2012, pp. 17-30"},{"key":"17_CR12","doi-asserted-by":"crossref","unstructured":"Krauthgamer, R., (Seffi) Naor, J., et al.: Partitioning graphs into balanced components. In: SODA 2009, pp. 942\u2013949 (2009)","DOI":"10.1137\/1.9781611973068.102"},{"key":"17_CR13","doi-asserted-by":"crossref","unstructured":"Martella, C., Logothetis, D., et al.: Spinner: Scalable graph partitioning in the cloud. In: ICDE 2017, pp. 1083\u20131094 (2017)","DOI":"10.1109\/ICDE.2017.153"},{"key":"17_CR14","doi-asserted-by":"crossref","unstructured":"Pacaci, A., Tamer \u00d6zsu, M.: Experimental analysis of streaming algorithms for graph partitioning. In: SIGMOD 2019, pp. 1375\u20131392 (2019)","DOI":"10.1145\/3299869.3300076"},{"key":"17_CR15","doi-asserted-by":"crossref","unstructured":"R\u00e4cke, H.: Optimal hierarchical decompositions for congestion minimization in networks. In: STOC 2008, pp. 255\u2013264 (2008)","DOI":"10.1145\/1374376.1374415"},{"issue":"5","key":"17_CR16","doi-asserted-by":"publisher","first-page":"1436","DOI":"10.1137\/S1064827593255135","volume":"18","author":"HD Simon","year":"1997","unstructured":"Simon, H.D., Teng, S.-H.: How good is recursive bisection? SIAM J. Sci. Comput. 18(5), 1436\u20131445 (1997)","journal-title":"SIAM J. Sci. Comput."},{"issue":"1","key":"17_CR17","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1137\/0805002","volume":"5","author":"F Alizadeh","year":"1995","unstructured":"Alizadeh, F.: Interior point methods in semidefinite programming with applications to combinatorial optimization. SIAM J. Optim. 5(1), 13\u201351 (1995)","journal-title":"SIAM J. Optim."}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-981-96-1093-8_17","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,20]],"date-time":"2025-02-20T11:47:01Z","timestamp":1740052021000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-981-96-1093-8_17"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025]]},"ISBN":["9789819610921","9789819610938"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/978-981-96-1093-8_17","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2025]]},"assertion":[{"value":"20 February 2025","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"COCOON","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Computing and Combinatorics Conference","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Shanghai","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"China","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2024","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"23 August 2024","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"25 August 2024","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"30","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"cocoon2024","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/anl.sjtu.edu.cn\/cocoon2024\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}