{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T22:01:49Z","timestamp":1743112909483,"version":"3.40.3"},"publisher-location":"Cham","reference-count":22,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030602444"},{"type":"electronic","value":"9783030602451"}],"license":[{"start":{"date-parts":[[2020,1,1]],"date-time":"2020-01-01T00:00:00Z","timestamp":1577836800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,1,1]],"date-time":"2020-01-01T00:00:00Z","timestamp":1577836800000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2020]]},"DOI":"10.1007\/978-3-030-60245-1_3","type":"book-chapter","created":{"date-parts":[[2020,9,30]],"date-time":"2020-09-30T08:06:00Z","timestamp":1601453160000},"page":"31-46","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Parallel SCC Detection Based on Reusing Warps and Coloring Partitions on GPUs"],"prefix":"10.1007","author":[{"given":"Junteng","family":"Hou","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shupeng","family":"Wang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Guangjun","family":"Wu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bingnan","family":"Ma","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lei","family":"Zhang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,9,29]]},"reference":[{"issue":"2","key":"3_CR1","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1007\/s00778-014-0372-z","volume":"24","author":"Z Zhang","year":"2015","unstructured":"Zhang, Z., Yu, J.X., Qin, L., Chang, L., Lin, X.: I\/O efficient: computing SCCs in massive graphs. VLDB J.\u2014Int. J. Very Large Data Bases 24(2), 245\u2013270 (2015)","journal-title":"VLDB J.\u2014Int. J. Very Large Data Bases"},{"issue":"10","key":"3_CR2","doi-asserted-by":"publisher","first-page":"1225","DOI":"10.1109\/43.875347","volume":"19","author":"A Xie","year":"2000","unstructured":"Xie, A., Beerel, P.A.: Implicit enumeration of strongly connected components and an application to formal verification. IEEE Trans. Comput. Aided Des. Integr. Circuits Syst. 19(10), 1225\u20131230 (2000)","journal-title":"IEEE Trans. Comput. Aided Des. Integr. Circuits Syst."},{"key":"3_CR3","unstructured":"Orzan, S.: On distributed verification and verified distribution, Ph.D. dissertation, Center for Mathematics and Computer Science (2004)"},{"issue":"1\u20132","key":"3_CR4","doi-asserted-by":"publisher","first-page":"1161","DOI":"10.14778\/1920841.1920986","volume":"3","author":"W Fan","year":"2010","unstructured":"Fan, W., Li, J., Ma, S., Wang, H., Wu, Y.: Graph homomorphism revisited for graph matching. Proc. VLDB Endow. 3(1\u20132), 1161\u20131172 (2010)","journal-title":"Proc. VLDB Endow."},{"issue":"4","key":"3_CR5","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(4), 146\u2013160 (1972)","journal-title":"SIAM J. Comput."},{"key":"3_CR6","volume-title":"A Discipline of Programming","author":"EW Dijkstra","year":"1976","unstructured":"Dijkstra, E.W.: A Discipline of Programming, 1st edn. Prentice Hall, Englewood Cliffs (1976)","edition":"1"},{"key":"3_CR7","volume-title":"Introduction to Algorithms","author":"TH Cormen","year":"2009","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 3rd edn. The MIT Press, Cambridge (2009)","edition":"3"},{"issue":"1","key":"3_CR8","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1093\/logcom\/exp003","volume":"21","author":"J Barnat","year":"2011","unstructured":"Barnat, J., Chaloupka, J., Van De Pol, J.: Distributed algorithms for SCC decomposition. J. Logic Comput. 21(1), 23\u201344 (2011)","journal-title":"J. Logic Comput."},{"key":"3_CR9","doi-asserted-by":"crossref","unstructured":"Barnat, J., Bauch, P., Brim, L., Ceska, M.: Computing strongly connected components in parallel on CUDA. In: Sussman, A., Mueller, F., Beaumont, O., Kandemir, M.T., Nikolopoulos, D. (eds.) IPDPS 2011, pp. 544\u2013555. IEEE (2011)","DOI":"10.1109\/IPDPS.2011.59"},{"key":"3_CR10","unstructured":"Devshatwar, S., Amilkanthwar, M., Nasre, R.: GPU centric extensions for parallel strongly connected components computation. In: GPGPU@PPoPP 2016, pp. 2\u201311. ACM, Barcelona (2016). \nhttps:\/\/doi.org\/10.1145%2F2884045.2884048"},{"key":"3_CR11","doi-asserted-by":"crossref","unstructured":"Li, P., Chen, X, Shen, J., Fang, J., Tang, T., Yang, C.: High performance detection of strongly connected components in sparse graphs on GPUs. In: PMAM@PPoPP 2017, pp. 48\u201357. ACM, Texas (2017)","DOI":"10.1145\/3026937.3026941"},{"key":"3_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. 1\u201311. ACM, Denver (2013)","DOI":"10.1145\/2503210.2503246"},{"issue":"1","key":"3_CR13","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."},{"key":"3_CR14","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: 2014 International Parallel and Distributed Processing Symposium, pp. 550\u2013559. IEEE (2014)","DOI":"10.1109\/IPDPS.2014.64"},{"issue":"8","key":"3_CR15","doi-asserted-by":"publisher","first-page":"901","DOI":"10.1016\/j.jpdc.2005.03.007","volume":"65","author":"W Mclendon Iii","year":"2005","unstructured":"Mclendon Iii, 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":"3_CR16","doi-asserted-by":"crossref","unstructured":"Kumar, R., Novak, J., Tomkins, A.: Structure and evolution of online social networks. In: Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD 2006, pp. 611\u2013617. ACM, New York (2006)","DOI":"10.1145\/1150402.1150476"},{"key":"3_CR17","unstructured":"Bader, D.A., Madduri, K.: GTGraph: a synthetic graph generator suite, vol. 38 (2006)"},{"key":"3_CR18","doi-asserted-by":"crossref","unstructured":"Chakrabarti, D., Zhan, Y., Faloutsos, C.: R-MAT: a recursive model for graph mining. In: Proceedings of the 2004 SIAM International Conference on Data Mining, pp. 442\u2013446. SIAM (2004)","DOI":"10.1137\/1.9781611972740.43"},{"key":"3_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"465","DOI":"10.1007\/11602569_48","volume-title":"High Performance Computing \u2013 HiPC 2005","author":"DA Bader","year":"2005","unstructured":"Bader, D.A., Madduri, K.: Design and implementation of the HPCS graph analysis benchmark on symmetric multiprocessors. In: Bader, D.A., Parashar, M., Sridhar, V., Prasanna, V.K. (eds.) HiPC 2005. LNCS, vol. 3769, pp. 465\u2013476. Springer, Heidelberg (2005). \nhttps:\/\/doi.org\/10.1007\/11602569_48"},{"key":"3_CR20","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). \nhttps:\/\/doi.org\/10.1007\/3-540-45591-4_68"},{"key":"3_CR21","unstructured":"Leskovec, J., Krevl, A.: SNAP Datasets: Stanford Large Network Dataset Collection, vol. 6 (2014). \nhttp:\/\/snap.stanford.edu\/data\n\n. Accessed 2 Feb 2020"},{"key":"3_CR22","unstructured":"Koblenz Network Collection. \nhttp:\/\/konect.uni-koblenz.de\/\n\n. Accessed 2 Feb 2020"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Architectures for Parallel Processing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-60245-1_3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,9,30]],"date-time":"2020-09-30T08:11:41Z","timestamp":1601453501000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-030-60245-1_3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020]]},"ISBN":["9783030602444","9783030602451"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-60245-1_3","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2020]]},"assertion":[{"value":"29 September 2020","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"ICA3PP","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Algorithms and Architectures for Parallel Processing","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"New York, NY","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"USA","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2020","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2 October 2020","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"4 October 2020","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"20","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"ica3pp2020","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/www.cloud-conf.net\/ica3pp2020\/","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":"495","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":"142","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":"5","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":"29% - 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":"305","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":"10","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)"}}]}}