{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,22]],"date-time":"2025-08-22T05:09:02Z","timestamp":1755839342673,"version":"3.40.3"},"publisher-location":"Cham","reference-count":21,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783031087561"},{"type":"electronic","value":"9783031087578"}],"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-08757-8_40","type":"book-chapter","created":{"date-parts":[[2022,6,21]],"date-time":"2022-06-21T07:06:09Z","timestamp":1655795169000},"page":"476-483","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Partitioning Dense Graphs with\u00a0Hardware Accelerators"],"prefix":"10.1007","author":[{"given":"Xiaoyuan","family":"Liu","sequence":"first","affiliation":[]},{"given":"Hayato","family":"Ushijima-Mwesigwa","sequence":"additional","affiliation":[]},{"given":"Indradeep","family":"Ghosh","sequence":"additional","affiliation":[]},{"given":"Ilya","family":"Safro","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,6,15]]},"reference":[{"key":"40_CR1","unstructured":"Bader, D.A., Meyerhenke, H., Sanders, P., Wagner, D.: 10th DIMACS implementation challenge-graph partitioning and graph clustering (2011). https:\/\/www.cc.gatech.edu\/dimacs10\/"},{"key":"40_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1007\/978-3-319-49487-6_4","volume-title":"Algorithm Engineering","author":"A Bulu\u00e7","year":"2016","unstructured":"Bulu\u00e7, A., Meyerhenke, H., Safro, I., Sanders, P., Schulz, C.: Recent advances in graph partitioning. In: Kliemann, L., Sanders, P. (eds.) Algorithm Engineering. LNCS, vol. 9220, pp. 117\u2013158. Springer, Cham (2016). https:\/\/doi.org\/10.1007\/978-3-319-49487-6_4"},{"issue":"1","key":"40_CR3","first-page":"1","volume":"38","author":"TA Davis","year":"2011","unstructured":"Davis, T.A., Hu, Y.: The university of Florida sparse matrix collection. ACM Trans. Math. Softw. (TOMS) 38(1), 1\u201325 (2011)","journal-title":"ACM Trans. Math. Softw. (TOMS)"},{"key":"40_CR4","unstructured":"Fujitsu: Fujitsu Digital Annealer (2022). https:\/\/www.fujitsu.com\/global\/services\/business-services\/digital-annealer\/"},{"key":"40_CR5","unstructured":"Gurobi Optimization, I.: Gurobi optimizer reference manual (2018). https:\/\/www.gurobi.com\/"},{"key":"40_CR6","unstructured":"Gutfraind, A., Safro, I., Meyers, L.A.: Multiscale network generation. In: 2015 18th International Conference on Information Fusion, pp. 158\u2013165. IEEE (2015)"},{"issue":"1","key":"40_CR7","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1007\/s10589-017-9945-2","volume":"69","author":"WW Hager","year":"2017","unstructured":"Hager, W.W., Hungerford, J.T., Safro, I.: A multilevel bilinear programming algorithm for the vertex separator problem. Comput. Optim. Appl. 69(1), 189\u2013223 (2017). https:\/\/doi.org\/10.1007\/s10589-017-9945-2","journal-title":"Comput. Optim. Appl."},{"issue":"4","key":"40_CR8","doi-asserted-by":"publisher","first-page":"500","DOI":"10.1137\/S0895480199335829","volume":"12","author":"WW Hager","year":"1999","unstructured":"Hager, W.W., Krylyuk, Y.: Graph partitioning and continuous quadratic programming. SIAM J. Discret. Math. 12(4), 500\u2013523 (1999)","journal-title":"SIAM J. Discret. Math."},{"issue":"1","key":"40_CR9","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s13278-016-0332-2","volume":"6","author":"M Hamann","year":"2016","unstructured":"Hamann, M., Lindner, G., Meyerhenke, H., Staudt, C.L., Wagner, D.: Structure-preserving sparsification methods for social networks. Soc. Netw. Anal. Min. 6(1), 1\u201322 (2016). https:\/\/doi.org\/10.1007\/s13278-016-0332-2","journal-title":"Soc. Netw. Anal. Min."},{"issue":"1","key":"40_CR10","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1137\/S1064827595287997","volume":"20","author":"G Karypis","year":"1999","unstructured":"Karypis, G., Kumar, V.: A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM J. Sci. Comput. 20(1), 359\u2013392 (1999)","journal-title":"SIAM J. Sci. Comput."},{"key":"40_CR11","doi-asserted-by":"crossref","unstructured":"Karypis, G., Kumar, V.: Multilevel algorithms for multi-constraint graph partitioning. In: SC 1998: Proceedings of the 1998 ACM\/IEEE Conference on Supercomputing, p. 28. IEEE (1998)","DOI":"10.1109\/SC.1998.10018"},{"key":"40_CR12","doi-asserted-by":"crossref","unstructured":"Liu, X., Ushijima-Mwesigwa, H., Ghosh, I., Safro, I.: Partitioning dense graphs with hardware accelerators. arXiv preprint arXiv:2202.09420 (2022)","DOI":"10.1007\/978-3-031-08757-8_40"},{"key":"40_CR13","doi-asserted-by":"crossref","unstructured":"Liu, X., Ushijima-Mwesigwa, H., Mandal, A., Upadhyay, S., Safro, I., Roy, A.: Leveraging special-purpose hardware for local search heuristics. Computational Optimization and Applications (2022, to appear)","DOI":"10.1007\/s10589-022-00354-2"},{"key":"40_CR14","doi-asserted-by":"publisher","first-page":"5","DOI":"10.3389\/fphy.2014.00005","volume":"2","author":"A Lucas","year":"2014","unstructured":"Lucas, A.: Ising formulations of many np problems. Front. Phys. 2, 5 (2014)","journal-title":"Front. Phys."},{"issue":"1","key":"40_CR15","doi-asserted-by":"publisher","first-page":"24","DOI":"10.1016\/j.jalgor.2004.10.004","volume":"60","author":"I Safro","year":"2006","unstructured":"Safro, I., Ron, D., Brandt, A.: Graph minimum linear arrangement by multilevel weighted edge contractions. J. Algorithms 60(1), 24\u201341 (2006)","journal-title":"J. Algorithms"},{"key":"40_CR16","first-page":"2","volume":"19","author":"I Safro","year":"2015","unstructured":"Safro, I., Sanders, P., Schulz, C.: Advanced coarsening schemes for graph partitioning. ACM J. Exp. Algorithm. (JEA) 19, 2 (2015)","journal-title":"ACM J. Exp. Algorithm. (JEA)"},{"key":"40_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"164","DOI":"10.1007\/978-3-642-38527-8_16","volume-title":"Experimental Algorithms","author":"P Sanders","year":"2013","unstructured":"Sanders, P., Schulz, C.: Think locally, act globally: highly balanced graph partitioning. In: Bonifaci, V., Demetrescu, C., Marchetti-Spaccamela, A. (eds.) SEA 2013. LNCS, vol. 7933, pp. 164\u2013175. Springer, Heidelberg (2013). https:\/\/doi.org\/10.1007\/978-3-642-38527-8_16"},{"key":"40_CR18","doi-asserted-by":"publisher","first-page":"482","DOI":"10.1137\/17M1152735","volume":"17","author":"R Shaydulin","year":"2019","unstructured":"Shaydulin, R., Chen, J., Safro, I.: Relaxation-based coarsening for multilevel hypergraph partitioning. SIAM Multiscale Model. Simul. 17, 482\u2013506 (2019)","journal-title":"SIAM Multiscale Model. Simul."},{"issue":"4","key":"40_CR19","doi-asserted-by":"publisher","first-page":"508","DOI":"10.1017\/nws.2016.20","volume":"4","author":"CL Staudt","year":"2016","unstructured":"Staudt, C.L., Sazonovs, A., Meyerhenke, H.: NetworKit: a tool suite for large-scale complex network analysis. Netw. Sci. 4(4), 508\u2013530 (2016)","journal-title":"Netw. Sci."},{"key":"40_CR20","doi-asserted-by":"crossref","unstructured":"Ushijima-Mwesigwa, H., Negre, C.F., Mniszewski, S.M.: Graph partitioning using quantum annealing on the D-Wave system. In: Proceedings of the Second International Workshop on Post Moores Era Supercomputing, pp. 22\u201329 (2017)","DOI":"10.1145\/3149526.3149531"},{"key":"40_CR21","unstructured":"Walshaw, C.: The graph partitioning archive (2009). https:\/\/chriswalshaw.co.uk\/partition\/"}],"container-title":["Lecture Notes in Computer Science","Computational Science \u2013 ICCS 2022"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-08757-8_40","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,16]],"date-time":"2023-05-16T11:06:34Z","timestamp":1684235194000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-08757-8_40"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022]]},"ISBN":["9783031087561","9783031087578"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-08757-8_40","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2022]]},"assertion":[{"value":"15 June 2022","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"ICCS","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Computational Science","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"London","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"United Kingdom","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":"21 June 2022","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"23 June 2022","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"22","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"iccs-computsci2022","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/www.iccs-meeting.org\/iccs2022\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"474","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"175","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"78","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"37% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"2.8","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}