{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,1]],"date-time":"2025-10-01T16:23:33Z","timestamp":1759335813057,"version":"3.40.3"},"publisher-location":"Cham","reference-count":22,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030293994"},{"type":"electronic","value":"9783030294007"}],"license":[{"start":{"date-parts":[[2019,1,1]],"date-time":"2019-01-01T00:00:00Z","timestamp":1546300800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2019,1,1]],"date-time":"2019-01-01T00:00:00Z","timestamp":1546300800000},"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":[[2019]]},"DOI":"10.1007\/978-3-030-29400-7_27","type":"book-chapter","created":{"date-parts":[[2019,8,18]],"date-time":"2019-08-18T23:02:41Z","timestamp":1566169361000},"page":"377-390","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Graph Coloring Using GPUs"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4215-0651","authenticated-orcid":false,"given":"Meghana Aparna","family":"Sistla","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5949-0046","authenticated-orcid":false,"given":"V. Krishna","family":"Nandivada","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2019,8,13]]},"reference":[{"key":"27_CR1","unstructured":"Biggs, N.: Some heuristics for graph colouring. In: Nelson, R., Wilson, R.J. (eds.) Graph Colourings, pp. 87\u201396 (1990)"},{"issue":"10\u201311","key":"27_CR2","doi-asserted-by":"publisher","first-page":"576","DOI":"10.1016\/j.parco.2012.07.001","volume":"38","author":"\u00dcV \u00c7ataly\u00fcrek","year":"2012","unstructured":"\u00c7ataly\u00fcrek, \u00dc.V., Feo, J., Gebremedhin, A.H., Halappanavar, M., Pothen, A.: Graph coloring algorithms for multi-core and massively multithreaded architectures. Parallel Comput. 38(10\u201311), 576\u2013594 (2012)","journal-title":"Parallel Comput."},{"key":"27_CR3","doi-asserted-by":"publisher","first-page":"98","DOI":"10.1145\/872726.806984","volume":"17","author":"GJ Chaitin","year":"1982","unstructured":"Chaitin, G.J.: Register allocation & spilling via graph coloring. ACM SIGPLAN Not. 17, 98\u2013105 (1982)","journal-title":"ACM SIGPLAN Not."},{"key":"27_CR4","doi-asserted-by":"crossref","unstructured":"Chakrabarti, D., Zhan, Y., Faloutsos, C.: R-MAT: a recursive model for graph mining. In: ICDM, pp. 442\u2013446. SIAM (2004)","DOI":"10.1137\/1.9781611972740.43"},{"issue":"2","key":"27_CR5","first-page":"51","volume":"3","author":"D Chalupa","year":"2011","unstructured":"Chalupa, D.: On the ability of graph coloring heuristics to find substructures in social networks. Inf. Sci. Technol. Bull. ACM Slovak. 3(2), 51\u201354 (2011)","journal-title":"Inf. Sci. Technol. Bull. ACM Slovak."},{"issue":"1","key":"27_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 TOMS 38(1), 1 (2011)","journal-title":"ACM TOMS"},{"key":"27_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"745","DOI":"10.1007\/BFb0056916","volume-title":"Parallel Problem Solving from Nature \u2014 PPSN V","author":"R\u00cb Dorne","year":"1998","unstructured":"Dorne, R.\u00cb., Hao, J.-K.: A new genetic local search algorithm for graph coloring. In: Eiben, A.E., B\u00e4ck, T., Schoenauer, M., Schwefel, H.-P. (eds.) PPSN 1998. LNCS, vol. 1498, pp. 745\u2013754. Springer, Heidelberg (1998). https:\/\/doi.org\/10.1007\/BFb0056916"},{"issue":"12","key":"27_CR8","doi-asserted-by":"publisher","first-page":"1131","DOI":"10.1002\/1096-9128(200010)12:12<1131::AID-CPE528>3.0.CO;2-2","volume":"12","author":"AH Gebremedhin","year":"2000","unstructured":"Gebremedhin, A.H., Manne, F.: Scalable parallel graph coloring algorithms. Concurr. Pract. Exp. 12(12), 1131\u20131146 (2000)","journal-title":"Concurr. Pract. Exp."},{"issue":"8","key":"27_CR9","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1145\/2038037.1941597","volume":"46","author":"AVP Grosset","year":"2011","unstructured":"Grosset, A.V.P., Zhu, P., Liu, S., Venkatasubramanian, S., Hall, M.: Evaluating graph coloring on GPUs. ACM SIGPLAN Not. 46(8), 297\u2013298 (2011)","journal-title":"ACM SIGPLAN Not."},{"issue":"39","key":"27_CR10","first-page":"851","volume":"3","author":"M Harris","year":"2007","unstructured":"Harris, M., Sengupta, S., Owens, J.D.: Parallel prefix sum (scan) with CUDA. GPU gems 3(39), 851\u2013876 (2007)","journal-title":"GPU gems"},{"issue":"3","key":"27_CR11","doi-asserted-by":"publisher","first-page":"654","DOI":"10.1137\/0914041","volume":"14","author":"MT Jones","year":"1993","unstructured":"Jones, M.T., Plassmann, P.E.: A parallel graph coloring heuristic. SIAM J. Sci. Comput. 14(3), 654\u2013669 (1993)","journal-title":"SIAM J. Sci. Comput."},{"issue":"5","key":"27_CR12","doi-asserted-by":"publisher","first-page":"753","DOI":"10.1016\/0167-8191(94)90004-3","volume":"20","author":"MT Jones","year":"1994","unstructured":"Jones, M.T., Plassmann, P.E.: Scalable iterative solution of sparse linear systems. Parallel Comput. 20(5), 753\u2013773 (1994)","journal-title":"Parallel Comput."},{"key":"27_CR13","doi-asserted-by":"crossref","unstructured":"Li, P., et al.: High performance parallel graph coloring on GPGPUs. In: IPDPS Workshops, pp. 845\u2013854. IEEE (2016)","DOI":"10.1109\/IPDPSW.2016.11"},{"issue":"4","key":"27_CR14","first-page":"1036","volume":"15","author":"M Luby","year":"1986","unstructured":"Luby, M.: A simple parallel algorithm for the maximal independent set problem. J. Comput. 15(4), 1036\u20131053 (1986)","journal-title":"J. Comput."},{"key":"27_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"332","DOI":"10.1007\/BFb0095354","volume-title":"Applied Parallel Computing Large Scale Scientific and Industrial Problems","author":"F Manne","year":"1998","unstructured":"Manne, F.: A parallel algorithm for computing the extremal eigenvalues of very large sparse matrices. In: K\u00e5gstr\u00f6m, B., Dongarra, J., Elmroth, E., Wa\u015bniewski, J. (eds.) PARA 1998. LNCS, vol. 1541, pp. 332\u2013336. Springer, Heidelberg (1998). https:\/\/doi.org\/10.1007\/BFb0095354"},{"issue":"1\u20132","key":"27_CR16","first-page":"11","volume":"48","author":"D Marx","year":"2004","unstructured":"Marx, D.: Graph colouring problems and their applications in scheduling. Period. Polytech. Electr. Eng. 48(1\u20132), 11\u201316 (2004)","journal-title":"Period. Polytech. Electr. Eng."},{"issue":"4","key":"27_CR17","doi-asserted-by":"publisher","first-page":"344","DOI":"10.1287\/ijoc.8.4.344","volume":"8","author":"A Mehrotra","year":"1996","unstructured":"Mehrotra, A., Trick, M.A.: A column generation approach for graph coloring. INFORMS J. Comput. 8(4), 344\u2013354 (1996)","journal-title":"INFORMS J. Comput."},{"key":"27_CR18","doi-asserted-by":"crossref","unstructured":"Nasre, R., Burtscher, M., Pingali, K.: Data-driven versus topology-driven irregular computations on GPUs. In: IPDPS, pp. 463\u2013474. IEEE (2013)","DOI":"10.1109\/IPDPS.2013.28"},{"key":"27_CR19","volume-title":"CuSPARSE Library","author":"C Nvidia","year":"2014","unstructured":"Nvidia, C.: CuSPARSE Library. NVIDIA Corporation, Santa Clara (2014)"},{"key":"27_CR20","doi-asserted-by":"crossref","unstructured":"Philipsen, W., Stok, L.: Graph coloring using neural networks. In: IEEE International Sympoisum on Circuits and Systems, pp. 1597\u20131600. IEEE (1991)","DOI":"10.1109\/ISCAS.1991.176684"},{"key":"27_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"414","DOI":"10.1007\/978-3-662-48096-0_32","volume-title":"Euro-Par 2015: Parallel Processing","author":"G Rokos","year":"2015","unstructured":"Rokos, G., Gorman, G., Kelly, P.H.J.: A fast and scalable graph coloring algorithm for multi-core and many-core architectures. In: Tr\u00e4ff, J.L., Hunold, S., Versaci, F. (eds.) Euro-Par 2015. LNCS, vol. 9233, pp. 414\u2013425. Springer, Heidelberg (2015). https:\/\/doi.org\/10.1007\/978-3-662-48096-0_32"},{"key":"27_CR22","doi-asserted-by":"crossref","unstructured":"Sistla, M.A., Nandivada, V.K.: Artifact for Graph Coloring using GPUs (2019). https:\/\/doi.org\/10.6084\/m9.figshare.8486123","DOI":"10.1007\/978-3-030-29400-7_27"}],"container-title":["Lecture Notes in Computer Science","Euro-Par 2019: Parallel Processing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-29400-7_27","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,7,22]],"date-time":"2024-07-22T04:30:10Z","timestamp":1721622610000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-29400-7_27"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019]]},"ISBN":["9783030293994","9783030294007"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-29400-7_27","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2019]]},"assertion":[{"value":"13 August 2019","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":"G\u00f6ttingen","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Germany","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2019","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"26 August 2019","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"30 August 2019","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"25","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"europar2019","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/europar.org\/","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":"142","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":"36","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":"0","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":"25% - 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":"3,94","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":"4,27","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)"}},{"value":"double blind review in two cases","order":10,"name":"additional_info_on_review_process","label":"Additional Info on Review Process","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}