{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,11,13]],"date-time":"2026-11-13T04:13:21Z","timestamp":1794543201783,"version":"4.9.1"},"publisher-location":"Cham","reference-count":21,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783319589428","type":"print"},{"value":"9783319589435","type":"electronic"}],"license":[{"start":{"date-parts":[[2017,1,1]],"date-time":"2017-01-01T00:00:00Z","timestamp":1483228800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2017,1,1]],"date-time":"2017-01-01T00:00:00Z","timestamp":1483228800000},"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":[[2017]]},"DOI":"10.1007\/978-3-319-58943-5_42","type":"book-chapter","created":{"date-parts":[[2017,5,27]],"date-time":"2017-05-27T04:42:07Z","timestamp":1495860127000},"page":"519-531","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Parametric Multi-step Scheme for GPU-Accelerated Graph Decomposition into Strongly Connected Components"],"prefix":"10.1007","author":[{"given":"Stefano","family":"Aldegheri","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ji\u0159\u00ed","family":"Barnat","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Nicola","family":"Bombieri","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Federico","family":"Busato","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Milan","family":"\u010ce\u0161ka","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2017,5,28]]},"reference":[{"key":"42_CR1","unstructured":"Bader, D.A., Madduri, K.: GTgraph: a synthetic graph generator suite. Technical report GA 30332, Georgia Institute of Technology, Atlanta (2006)"},{"key":"42_CR2","doi-asserted-by":"crossref","unstructured":"Barnat, J., Bauch, P., Brim, L., \u010ce\u0161ka, M.: Computing strongly connected components in parallel on CUDA. In: IPDPS 2011, pp. 541\u2013552. IEEE Computer Society (2011)","DOI":"10.1109\/IPDPS.2011.59"},{"key":"42_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"316","DOI":"10.1007\/978-3-540-70952-7_22","volume-title":"Formal Methods: Applications and Technology","author":"J Barnat","year":"2007","unstructured":"Barnat, J., Moravec, P.: Parallel algorithms for finding SCCs in implicitly given graphs. In: Brim, L., Haverkort, B., Leucker, M., Pol, J. (eds.) FMICS 2006. LNCS, vol. 4346, pp. 316\u2013330. Springer, Heidelberg (2007). doi:10.1007\/978-3-540-70952-7_22"},{"key":"42_CR4","doi-asserted-by":"crossref","unstructured":"Bloemen, V., Laarman, A., van de Pol, J.: Multi-core on-the-fly SCC decomposition. In: PPoPP 2016, pp. 8:1\u20138:12. ACM (2016)","DOI":"10.1145\/3016078.2851161"},{"issue":"7","key":"42_CR5","doi-asserted-by":"publisher","first-page":"1826","DOI":"10.1109\/TPDS.2014.2330597","volume":"26","author":"F Busato","year":"2015","unstructured":"Busato, F., Bombieri, N.: BFS-4K: an efficient implementation of BFS for kepler GPU architectures. IEEE Trans. Parallel Distrib. Syst. 26(7), 1826\u20131838 (2015). ISSN 1045-9219","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"issue":"1","key":"42_CR6","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 (2011)","journal-title":"ACM Trans. Math. Softw. (TOMS)"},{"key":"42_CR7","doi-asserted-by":"publisher","DOI":"10.1090\/dimacs\/074","volume-title":"The Shortest Path Problem: Ninth DIMACS Implementation Challenge","author":"C Demetrescu","year":"2009","unstructured":"Demetrescu, C., Goldberg, A.V., Johnson, D.S.: The Shortest Path Problem: Ninth DIMACS Implementation Challenge, vol. 74. American Mathematical Society, Providence (2009)"},{"key":"42_CR8","doi-asserted-by":"crossref","unstructured":"Devshatwar, S., Amilkanthwar, M., Nasre, R.: GPU centric extensions for parallel strongly connected components computation. In: GPGPU 2016, pp. 2\u201311. ACM (2016)","DOI":"10.1145\/2884045.2884048"},{"key":"42_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"505","DOI":"10.1007\/3-540-45591-4_68","volume-title":"Parallel and Distributed Processing","author":"LK Fleischer","year":"2000","unstructured":"Fleischer, L.K., Hendrickson, B., P\u0131nar, A.: On identifying strongly connected components in parallel. In: Rolim, J. (ed.) IPDPS 2000. LNCS, vol. 1800, pp. 505\u2013511. Springer, Heidelberg (2000). doi:10.1007\/3-540-45591-4_68"},{"key":"42_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1007\/978-3-540-77220-0_21","volume-title":"High Performance Computing \u2013 HiPC 2007","author":"P Harish","year":"2007","unstructured":"Harish, P., Narayanan, P.J.: Accelerating large graph algorithms on the GPU using CUDA. In: Aluru, S., Parashar, M., Badrinath, R., Prasanna, V.K. (eds.) HiPC 2007. LNCS, vol. 4873, pp. 197\u2013208. Springer, Heidelberg (2007). doi:10.1007\/978-3-540-77220-0_21"},{"key":"42_CR11","doi-asserted-by":"crossref","unstructured":"Hong, S., Kim, S., Oguntebi, T., Olukotun, K.: Accelerating CUDA graph algorithms at maximum warp. In: PPoPP 2011, pp. 267\u2013276. ACM (2011)","DOI":"10.1145\/2038037.1941590"},{"key":"42_CR12","doi-asserted-by":"crossref","unstructured":"Hong, S., Rodia, N.C., Olukotun, K.: On fast parallel detection of strongly connected components (SCC) in small-world graphs. In: SC 2013, pp. 92:1\u201392:11. ACM (2013)","DOI":"10.1145\/2503210.2503246"},{"key":"42_CR13","doi-asserted-by":"crossref","unstructured":"Kunegis, J.: Konect: the koblenz network collection. In: WWW 2013, pp. 1343\u20131350. ACM (2013)","DOI":"10.1145\/2487788.2488173"},{"key":"42_CR14","doi-asserted-by":"crossref","unstructured":"Leskovec, J., Sosi\u010d, R.: SNAP: a general purpose network analysis and graph mining library in C++. http:\/\/snap.stanford.edu\/snap. Accessed May 2016","DOI":"10.1145\/2898361"},{"issue":"1","key":"42_CR15","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.sysarc.2013.10.014","volume":"60","author":"G Li","year":"2014","unstructured":"Li, G., Zhu, Z., Cong, Z., Yang, F.: Efficient decomposition of strongly connected components on GPUs. J. Syst. Architect. 60(1), 1\u201310 (2014)","journal-title":"J. Syst. Architect."},{"issue":"1","key":"42_CR16","doi-asserted-by":"publisher","first-page":"136","DOI":"10.1109\/TPDS.2013.41","volume":"25","author":"X Liu","year":"2014","unstructured":"Liu, X., et al.: IMGPU: GPU accelerated influence maximization in large-scale social networks. IEEE Trans. Parallel Distrib. Syst. 25(1), 136\u2013145 (2014)","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"issue":"8","key":"42_CR17","doi-asserted-by":"publisher","first-page":"901","DOI":"10.1016\/j.jpdc.2005.03.007","volume":"65","author":"W McLendon","year":"2005","unstructured":"McLendon, W., Hendrickson, B., Plimpton, S.J., Rauchwerger, L.: Finding strongly connected components in distributed graphs. J. Parallel Distrib. Comput. 65(8), 901\u2013910 (2005)","journal-title":"J. Parallel Distrib. Comput."},{"key":"42_CR18","doi-asserted-by":"crossref","unstructured":"Merrill, D., Garland, M., Grimshaw, A.: Scalable GPU graph traversal. In: PPoPP 2012, pp. 117\u2013128. ACM (2012)","DOI":"10.1145\/2370036.2145832"},{"key":"42_CR19","unstructured":"Orzan, S.: On distributed verification and verified distribution. Ph.D. thesis, Free University of Amsterdam (2004)"},{"key":"42_CR20","doi-asserted-by":"crossref","unstructured":"Slota, G.M., Rajamanickam, S., Madduri, K.: BFS and coloring-based parallel algorithms for strongly connected components and related problems. In: IPDPS 2014, pp. 550\u2013559. IEEE Computer Society (2014)","DOI":"10.1109\/IPDPS.2014.64"},{"issue":"2","key":"42_CR21","doi-asserted-by":"publisher","first-page":"146","DOI":"10.1137\/0201010","volume":"1","author":"R Tarjan","year":"1972","unstructured":"Tarjan, R.: Depth-first search and linear graph algorithms. SIAM J. Comput. 1(2), 146\u2013160 (1972)","journal-title":"SIAM J. Comput."}],"container-title":["Lecture Notes in Computer Science","Euro-Par 2016: Parallel Processing Workshops"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-58943-5_42","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,27]],"date-time":"2021-05-27T20:29:46Z","timestamp":1622147386000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-58943-5_42"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017]]},"ISBN":["9783319589428","9783319589435"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-58943-5_42","relation":{"is-part-of":[{"id-type":"doi","id":"https:\/\/doi.org\/10.1007\/978-3-319-58943-5","asserted-by":"object"}]},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017]]},"assertion":[{"value":"28 May 2017","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":"Grenoble","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"France","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2016","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"24 August 2016","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"26 August 2016","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":"europar2016","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/europar2016.inria.fr\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}