{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,20]],"date-time":"2025-06-20T11:46:15Z","timestamp":1750419975313,"version":"3.40.3"},"publisher-location":"Cham","reference-count":24,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031695827"},{"type":"electronic","value":"9783031695834"}],"license":[{"start":{"date-parts":[[2024,1,1]],"date-time":"2024-01-01T00:00:00Z","timestamp":1704067200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,1,1]],"date-time":"2024-01-01T00:00:00Z","timestamp":1704067200000},"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":[[2024]]},"DOI":"10.1007\/978-3-031-69583-4_6","type":"book-chapter","created":{"date-parts":[[2024,8,25]],"date-time":"2024-08-25T19:02:05Z","timestamp":1724612525000},"page":"74-87","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["GPU-Accelerated BFS for\u00a0Dynamic Networks"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0009-0008-9753-0898","authenticated-orcid":false,"given":"Filippo","family":"Ziche","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3256-5885","authenticated-orcid":false,"given":"Nicola","family":"Bombieri","sequence":"additional","affiliation":[]},{"given":"Federico","family":"Busato","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9843-7638","authenticated-orcid":false,"given":"Rosalba","family":"Giugno","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,8,26]]},"reference":[{"unstructured":"Network repository. https:\/\/networkrepository.com\/","key":"6_CR1"},{"unstructured":"Suite sparse matrix collection. https:\/\/sparse.tamu.edu\/","key":"6_CR2"},{"key":"6_CR3","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1007\/978-3-662-48350-3_14","volume":"9294","author":"E Bergamini","year":"2015","unstructured":"Bergamini, E., Meyerhenke, H.: Fully-dynamic approximation of betweenness centrality. Lect. Notes Comput. Sci. 9294, 155\u2013166 (2015)","journal-title":"Lect. Notes Comput. Sci."},{"issue":"6","key":"6_CR4","doi-asserted-by":"publisher","first-page":"1860","DOI":"10.1109\/TPDS.2021.3131677","volume":"34","author":"M Besta","year":"2023","unstructured":"Besta, M., Fischer, M., Kalavri, V., Kapralov, M., Hoefler, T.: Practice of streaming processing of dynamic graphs: concepts, models, and systems. IEEE Trans. Parallel Distrib. Syst. 34(6), 1860\u20131876 (2023)","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"doi-asserted-by":"crossref","unstructured":"Busato, F., Green, O., Bombieri, N., Bader, D.A.: Hornet: an efficient data structure for dynamic sparse graphs and matrices on GPUs. In: 2018 IEEE High Performance Extreme Computing Conference (2018)","key":"6_CR5","DOI":"10.1109\/HPEC.2018.8547541"},{"unstructured":"Cormen, T., Leiserson, C., Rivest, R., Stein, C.: Introduction to Algorithms. MIT press (2009)","key":"6_CR6"},{"issue":"4","key":"6_CR7","doi-asserted-by":"publisher","first-page":"578","DOI":"10.1145\/1198513.1198519","volume":"2","author":"C Demetrescu","year":"2006","unstructured":"Demetrescu, C., Italiano, G.F.: Experimental analysis of dynamic all pairs shortest path algorithms. ACM Trans. Algorithms 2(4), 578\u2013601 (2006)","journal-title":"ACM Trans. Algorithms"},{"key":"6_CR8","doi-asserted-by":"publisher","first-page":"338","DOI":"10.1007\/978-3-642-22300-6_29","volume":"6844","author":"C Doll","year":"2011","unstructured":"Doll, C., Hartmann, T., Wagner, D.: Fully-dynamic hierarchical graph clustering using cut trees. Lect. Notes Comput. Sci. 6844, 338\u2013349 (2011)","journal-title":"Lect. Notes Comput. Sci."},{"doi-asserted-by":"crossref","unstructured":"Gaihre, A., Wu, Z., Yao, F., Liu, H.: XBFS: exploring runtime optimizations for breadth-first search on GPUs. In: Proceedings of the 28th International Symposium on High-Performance Parallel and Distributed Computing, pp. 121\u2013131 (2019)","key":"6_CR9","DOI":"10.1145\/3307681.3326606"},{"doi-asserted-by":"crossref","unstructured":"Green, O.: Inverse-deletion BFS-revisiting static graph BFS traversals with dynamic graph operations. In: IEEE High Performance Extreme Computing Conference (2021)","key":"6_CR10","DOI":"10.1109\/HPEC49654.2021.9622864"},{"doi-asserted-by":"crossref","unstructured":"Green, O., Bader, D.A.: cuSTINGER: supporting dynamic graph algorithms for GPUs. In: IEEE High Performance Extreme Computing Conference (2016)","key":"6_CR11","DOI":"10.1109\/HPEC.2016.7761622"},{"doi-asserted-by":"crossref","unstructured":"Grinten Van\u00a0Der, A., Bergamini, E., Green, O., Bader, D.A., Meyerhenke, H.: Scalable katz ranking computation in large static and dynamic graphs. ACM J. Exper. Algorithmics 27(1) (2022)","key":"6_CR12","DOI":"10.1145\/3524615"},{"doi-asserted-by":"crossref","unstructured":"Hong, S., Kim, S.K., Oguntebi, T., Olukotun, K.: Accelerating CUDA graph algorithms at maximum warp. In: ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, pp. 267\u2013276 (2011)","key":"6_CR13","DOI":"10.1145\/2038037.1941590"},{"doi-asserted-by":"crossref","unstructured":"Hsieh, C.Y., Cheng, P.H., Chang, C.M., Kuo, S.Y.: A decentralized frontier queue for improving scalability of breadth-first-search on GPUs. In: Design, Automation and Test in Europe (2023)","key":"6_CR14","DOI":"10.23919\/DATE56975.2023.10137054"},{"key":"6_CR15","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1227161.1370597","volume":"12","author":"I Krommidas","year":"2008","unstructured":"Krommidas, I., Zaroliagis, C.: An experimental study of algorithms for fully dynamic transitive closure. ACM J. Exp. Algorithmics 12, 1\u201322 (2008)","journal-title":"ACM J. Exp. Algorithmics"},{"doi-asserted-by":"crossref","unstructured":"Luo, L., Wong, M., Hwu, W.M.: An effective GPU implementation of breadth-first search. In: Design Automation Conference, pp. 52\u201355 (2010)","key":"6_CR16","DOI":"10.1145\/1837274.1837289"},{"doi-asserted-by":"crossref","unstructured":"Macko, P., Marathe, V.J., Margo, D.W., Seltzer, M.I.: Llama: efficient graph analytics using large multiversioned arrays. In: International Conference on Data Engineering, pp. 363\u2013374 (2015)","key":"6_CR17","DOI":"10.1109\/ICDE.2015.7113298"},{"doi-asserted-by":"crossref","unstructured":"Merrill, D., Garland, M., Grimshaw, A.: High-performance and scalable GPU graph traversal. ACM Trans. Parallel Comput. 1(2) (2015)","key":"6_CR18","DOI":"10.1145\/2717511"},{"doi-asserted-by":"crossref","unstructured":"Todling, D., Winter, M., Steinberger, M.: Breadth-first search on dynamic graphs using dynamic parallelism on the GPU. In: 2019 IEEE High Performance Extreme Computing Conference (2019)","key":"6_CR19","DOI":"10.1109\/HPEC.2019.8916476"},{"doi-asserted-by":"crossref","unstructured":"Wang, Y., et al.: Gunrock: GPU graph analytics. ACM Trans. Parallel Comput. 4(1), 3:1\u20133:49 (2017). http:\/\/escholarship.org\/uc\/item\/9gj6r1dj","key":"6_CR20","DOI":"10.1145\/3108140"},{"doi-asserted-by":"crossref","unstructured":"Wen, H., Zhang, W.: Improving parallelism of breadth first search (BFS) algorithm for accelerated performance on GPUs. In: 2019 IEEE High Performance Extreme Computing Conference (HPEC) (2019)","key":"6_CR21","DOI":"10.1109\/HPEC.2019.8916551"},{"doi-asserted-by":"crossref","unstructured":"Winter, M., Mlakar, D., Zayer, R., Seidel, H.P., Steinberger, M.: FaimGraph: high performance management of fully-dynamic graphs under tight memory constraints on the GPU. In: International Conference for High Performance Computing, Networking, Storage, and Analysis, pp. 754\u2014766 (2019)","key":"6_CR22","DOI":"10.1109\/SC.2018.00063"},{"doi-asserted-by":"crossref","unstructured":"Xie, W., Tian, Y., Sismanis, Y., Balmin, A., Haas, P.J.: Dynamic interaction graphs with probabilistic edge decay. In: International Conference on Data Engineering, vol. 2015-May, pp. 1143\u20131154 (2015)","key":"6_CR23","DOI":"10.1109\/ICDE.2015.7113363"},{"key":"6_CR24","doi-asserted-by":"publisher","first-page":"383","DOI":"10.1016\/j.jpdc.2017.09.007","volume":"120","author":"G Zhang","year":"2018","unstructured":"Zhang, G., Cheng, S., Shu, J., Hu, Q., Zheng, W.: Accelerating breadth-first graph search on a single server by dynamic edge trimming. J. Parallel Distrib. Comput. 120, 383\u2013394 (2018)","journal-title":"J. Parallel Distrib. Comput."}],"container-title":["Lecture Notes in Computer Science","Euro-Par 2024: Parallel Processing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-69583-4_6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,8,25]],"date-time":"2024-08-25T19:03:24Z","timestamp":1724612604000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-69583-4_6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024]]},"ISBN":["9783031695827","9783031695834"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-69583-4_6","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2024]]},"assertion":[{"value":"26 August 2024","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"Euro-Par","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"European Conference on Parallel Processing","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Madrid","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Spain","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":"26 August 2024","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"30 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":"europar2024","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/2024.euro-par.org\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}