{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,25]],"date-time":"2026-01-25T04:11:50Z","timestamp":1769314310632,"version":"3.49.0"},"reference-count":49,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2024,10,17]],"date-time":"2024-10-17T00:00:00Z","timestamp":1729123200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,10,17]],"date-time":"2024-10-17T00:00:00Z","timestamp":1729123200000},"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":["Int J Parallel Prog"],"published-print":{"date-parts":[[2025,2]]},"DOI":"10.1007\/s10766-024-00781-0","type":"journal-article","created":{"date-parts":[[2024,10,17]],"date-time":"2024-10-17T17:02:54Z","timestamp":1729184574000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Giraph-Based Distributed Algorithms for Coloring Large-Scale Graphs"],"prefix":"10.1007","volume":"53","author":[{"given":"Assia","family":"Brighen","sequence":"first","affiliation":[]},{"given":"Asma","family":"Chouikh","sequence":"additional","affiliation":[]},{"given":"Hamida","family":"Ikhlef","sequence":"additional","affiliation":[]},{"given":"Hachem","family":"Slimani","sequence":"additional","affiliation":[]},{"given":"Abdelmounaam","family":"Rezgui","sequence":"additional","affiliation":[]},{"given":"Hamamache","family":"Kheddouci","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,10,17]]},"reference":[{"key":"781_CR1","doi-asserted-by":"publisher","first-page":"102769","DOI":"10.1016\/j.parco.2021.102769","volume":"106","author":"S Acer","year":"2021","unstructured":"Acer, S., Boman, E., Glusa, Ch.A., et al.: Sphynx: a parallel multi-GPU graph partitioner for distributed-memory systems. Parallel. Comput. 106, 102769 (2021). https:\/\/doi.org\/10.1016\/j.parco.2021.102769","journal-title":"Parallel. Comput."},{"key":"781_CR2","unstructured":"Aslan, M., Baykan, N.: A performance comparison of graph coloring algorithms. In: ICAT\u20192016, 3rd International conference on advanced technology & Sciences, Konya, Turkey (2016)"},{"issue":"2","key":"781_CR3","doi-asserted-by":"publisher","first-page":"379","DOI":"10.1016\/S0377-2217(02)00832-9","volume":"151","author":"C Avanthay","year":"2003","unstructured":"Avanthay, C., Hertz, A., Zufferey, N.: A variable neighborhood search for graph coloring. Eur. J. Oper. Res. 151(2), 379\u2013388 (2003). https:\/\/doi.org\/10.1016\/S0377-2217(02)00832-9","journal-title":"Eur. J. Oper. Res."},{"key":"781_CR4","unstructured":"Avery, C.: Giraph: large-scale graph processing infrastructure on hadoop. In: Proceeding of the 2011 Hadoop Summit Santa Clara (2011)"},{"issue":"1\u20134","key":"781_CR5","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1023\/B:ANOR.0000032574.01332.98","volume":"130","author":"N Barnier","year":"2004","unstructured":"Barnier, N., Brisset, P.: Graph coloring for air traffic flow management. Ann. Oper. Res. 130(1\u20134), 163\u2013178 (2004). https:\/\/doi.org\/10.1023\/B:ANOR.0000032574.01332.98","journal-title":"Ann. Oper. Res."},{"key":"781_CR6","doi-asserted-by":"publisher","first-page":"102896","DOI":"10.1016\/j.parco.2022.102896","volume":"110","author":"I Bogle","year":"2022","unstructured":"Bogle, I., Slota, G., Boman, E., et al.: Parallel graph coloring algorithms for distributed GPU environments. Parallel Comput. 110, 102896 (2022). https:\/\/doi.org\/10.1016\/j.parco.2022.102896","journal-title":"Parallel Comput."},{"key":"781_CR7","doi-asserted-by":"publisher","unstructured":"Boman, E., Bozdag, D., Catalyurek, U., et\u00a0al.: A scalable parallel graph coloring algorithm for distributed memory computers. In: Euro-Par\u201905 Proceedings of the 11th international Euro-Par conference on parallel processing pp 241\u201325 (2005) https:\/\/doi.org\/10.1007\/11549468_29","DOI":"10.1007\/11549468_29"},{"issue":"4","key":"781_CR8","doi-asserted-by":"publisher","first-page":"515","DOI":"10.1016\/j.jpdc.2007.08.002","volume":"68","author":"D Bozdag","year":"2008","unstructured":"Bozdag, D., Gebremedhin, A., Manne, F., et al.: A framework for scalable greedy coloring on distributed-memory parallel computers. J. Parallel Distrib. Comput. 68(4), 515\u2013535 (2008). https:\/\/doi.org\/10.1016\/j.jpdc.2007.08.002","journal-title":"J. Parallel Distrib. Comput."},{"key":"781_CR9","doi-asserted-by":"publisher","first-page":"678","DOI":"10.22331\/q-2022-03-30-678","volume":"6","author":"S Bravyi","year":"2022","unstructured":"Bravyi, S., Kliesch, A., Koenig, R., et al.: Hybrid quantum-classical algorithms for approximate graph coloring. Quantum 6, 678 (2022). https:\/\/doi.org\/10.22331\/q-2022-03-30-678","journal-title":"Quantum"},{"key":"781_CR10","doi-asserted-by":"publisher","first-page":"4918","DOI":"10.1007\/s11227-019-02770-4","volume":"75","author":"A Brighen","year":"2019","unstructured":"Brighen, A., Slimani, H., Rezgui, A., et al.: Listing all maximal cliques in large graphs on vertex-centric model. J Supercomput. 75, 4918\u20134946 (2019). https:\/\/doi.org\/10.1007\/s11227-019-02770-4","journal-title":"J Supercomput."},{"key":"781_CR11","doi-asserted-by":"publisher","unstructured":"Brighen, A., Slimani, H., Rezgui, A., et\u00a0al.: A distributed large graph coloring algorithm on giraph. In: 2020 5th International conference on cloud computing and artificial intelligence: technologies and applications (CloudTech), Marrakesh, Morocco pp 1\u2013 (2020) https:\/\/doi.org\/10.1109\/CloudTech49835.2020.9365872","DOI":"10.1109\/CloudTech49835.2020.9365872"},{"issue":"1","key":"781_CR12","doi-asserted-by":"publisher","first-page":"875","DOI":"10.1007\/s10586-023-03988-x","volume":"27","author":"A Brighen","year":"2024","unstructured":"Brighen, A., Slimani, H., Rezgui, A., et al.: A new distributed graph coloring algorithm for large graphs. Cluster Comput. 27(1), 875\u2013891 (2024). https:\/\/doi.org\/10.1007\/s10586-023-03988-x","journal-title":"Cluster Comput."},{"key":"781_CR13","doi-asserted-by":"publisher","unstructured":"Br\u00e91az D,: New methods to color the vertices of a graph. Commun. ACM 22(4), 251\u2013256 (1979). https:\/\/doi.org\/10.1145\/359094.359101","DOI":"10.1145\/359094.359101"},{"key":"781_CR14","doi-asserted-by":"publisher","unstructured":"Chen, H., Zhou, P.: An ant algorithm for solving the four-coloring map problem. In: The 9th international conference on natural computation (ICNC) pp 491\u2013495 (2013) https:\/\/doi.org\/10.1109\/ICNC.2013.6818026","DOI":"10.1109\/ICNC.2013.6818026"},{"key":"781_CR15","doi-asserted-by":"publisher","unstructured":"Chen, W., Chen, W., Ashar, P., et\u00a0al.: Register allocation for intel processor graphics. In: CGO 2018 Proceedings of the 2018 International symposium on code generation and optimization pp 352\u2013364 (2018) https:\/\/doi.org\/10.1145\/3168806","DOI":"10.1145\/3168806"},{"key":"781_CR16","doi-asserted-by":"publisher","unstructured":"Deveci, M., Boman, E., Devine, K., et\u00a0al.: Parallel graph coloring for manycore architectures. In: 2016 IEEE International Parallel and Distributed Processing Symposium (IPDPS) pp 892\u2013901 (2016) https:\/\/doi.org\/10.1109\/IPDPS.2016.54","DOI":"10.1109\/IPDPS.2016.54"},{"key":"781_CR17","doi-asserted-by":"publisher","unstructured":"Gandhi, N., Misra, R.: Performance comparison of parallel graph coloring algorithms on bsp model using hadoop. In: 2015 International conference on computing, networking and communications, USA pp 110\u2013116. (2015) https:\/\/doi.org\/10.1109\/ICCNC.2015.7069325","DOI":"10.1109\/ICCNC.2015.7069325"},{"issue":"12","key":"781_CR18","first-page":"1131","volume":"12","author":"A Gebremedhin","year":"2000","unstructured":"Gebremedhin, A., Manne, F.: Scalable parallel graph coloring algorithms. Concurr. Comput. 12(12), 1131\u20131146 (2000)","journal-title":"Concurr. Comput."},{"key":"781_CR19","unstructured":"Giraph A (Accessed 01 Mars 2023) Apache giraph! https:\/\/giraph.apache.org"},{"issue":"2","key":"781_CR20","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1006\/jpdc.1996.0117","volume":"37","author":"J Gjertsen","year":"1996","unstructured":"Gjertsen, J., Jones, M.T., Plassmann, P.: Parallel heuristics for improved, balanced graph colorings. J. Parallel Distrib. Comput. 37(2), 171\u2013186 (1996). https:\/\/doi.org\/10.1006\/jpdc.1996.0117","journal-title":"J. Parallel Distrib. Comput."},{"key":"781_CR21","doi-asserted-by":"crossref","unstructured":"Gross, J., Yellen, J., Zhang, P.: Handbook of graph theory, 2nd edn. CRC Press Taylor & Francis Group (2014)","DOI":"10.1201\/b16132"},{"key":"781_CR22","doi-asserted-by":"publisher","unstructured":"Hasenplaugh W, Kaler T, Schardl T, et\u00a0al.: Ordering heuristics for parallel graph coloring. In: SPAA\u201914: Proceedings of the 26th ACM symposium on parallelism in algorithms and architectures pp. 166\u2013177. (2014) https:\/\/doi.org\/10.1145\/2612669.2612697","DOI":"10.1145\/2612669.2612697"},{"issue":"4","key":"781_CR23","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1007\/BF02239976","volume":"39","author":"A Hertz","year":"1987","unstructured":"Hertz, A., de Werra, D.: Using tabu search techniques for graph coloring. J Comput 39(4), 345\u201335 (1987). https:\/\/doi.org\/10.1007\/BF02239976","journal-title":"J Comput"},{"key":"781_CR24","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1007\/s10818-023-09334-w","volume":"25","author":"T Holtfort","year":"2023","unstructured":"Holtfort, T., Horsch, A.: Social science goes quantum: explaining human decision-making, cognitive biases and darwinian selection from a quantum perspective. J Bioeconomics. 25, 99\u2013116 (2023). https:\/\/doi.org\/10.1007\/s10818-023-09334-w","journal-title":"J Bioeconomics."},{"key":"781_CR25","doi-asserted-by":"publisher","unstructured":"H\u00e9brard E, Katsirelos G.: A hybrid approach for exact coloring of massive graphs. In: International conference on integration of constraint programming, artificial intelligence, and operations research (CPAIOR 2019) pp 374\u201339 (2019) https:\/\/doi.org\/10.1007\/978-3-030-19212-9_25","DOI":"10.1007\/978-3-030-19212-9_25"},{"issue":"3","key":"781_CR26","doi-asserted-by":"publisher","first-page":"654","DOI":"10.1137\/0914041","volume":"14","author":"M Jones","year":"1993","unstructured":"Jones, M., Plassmann, P.: A parallel graph coloring heuristic. SIAM J. Sci. Comput. 14(3), 654\u2013669 (1993). https:\/\/doi.org\/10.1137\/0914041","journal-title":"SIAM J. Sci. Comput."},{"key":"781_CR27","doi-asserted-by":"publisher","unstructured":"Karp, R.: Reducibility among combinatorial problems. complexity of computer computations pp 85\u201310 (1972) https:\/\/doi.org\/10.1007\/978-1-4684-2001-2_9","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"781_CR28","doi-asserted-by":"crossref","unstructured":"Kosowski, A., Manuszewski, K.: Classical graph coloring, In: Kubale, M. (ed.) Graph colorings, American mathematical society, Providence, chap\u00a01, pp 1\u201320 (2004)","DOI":"10.1090\/conm\/352\/06369"},{"key":"781_CR29","unstructured":"Leskovec, J., Krevl, A.: ((Accessed 01 Mars 2023)) Snap datasets: stanford large network dataset collection. (2014) http:\/\/snap.stanford.edu\/data"},{"key":"781_CR30","doi-asserted-by":"publisher","unstructured":"Liu, H., Su, C., Chu, A.: Fast quasi-biclique mining with giraph. In: BIGDATACONGRESS\u201913 Proceedings of the 2013 IEEE international congress on big data pp 347\u20133 (2013) https:\/\/doi.org\/10.1109\/BigData.Congress.2013.53","DOI":"10.1109\/BigData.Congress.2013.53"},{"key":"781_CR31","doi-asserted-by":"publisher","unstructured":"Luby M .: A simple parallel algorithm for the maximal independent set problem. In: Proceedings of the 17th annual ACM symposium on theory of computing 15(4):1036\u20131053 (1986) https:\/\/doi.org\/10.1145\/22145.22146","DOI":"10.1145\/22145.22146"},{"issue":"8","key":"781_CR32","doi-asserted-by":"publisher","first-page":"2189","DOI":"10.1016\/j.cor.2005.01.008","volume":"33","author":"C Lucet","year":"2006","unstructured":"Lucet, C., Mendes, F., Moukrim, A.: An exact method for graph coloring. Comput. Oper. Res. 33(8), 2189\u20132207 (2006). https:\/\/doi.org\/10.1016\/j.cor.2005.01.008","journal-title":"Comput. Oper. Res."},{"key":"781_CR33","doi-asserted-by":"publisher","unstructured":"Lunagariya, D., Somayajulu, D., Krishna, P.: Se-cda: A scalable and efficient community detection algorithm. In: 2014 IEEE international conference on big data (big data), Washington, DC, USA pp 877\u2013882. (2014) https:\/\/doi.org\/10.1109\/BigData.2014.7004318","DOI":"10.1109\/BigData.2014.7004318"},{"key":"781_CR34","doi-asserted-by":"publisher","unstructured":"Malewicz G, Austern M, Bik A, et\u00a0al.: Pregel: a system for large-scale graph processing. In: Proceedings of the 2010 ACM SIGMOD International conference on management of data, Indiana, USA pp 135\u2013146. (2010) https:\/\/doi.org\/10.1145\/1807167.1807184","DOI":"10.1145\/1807167.1807184"},{"key":"781_CR35","doi-asserted-by":"publisher","DOI":"10.4108\/eetsis.5437","author":"K Malhotra","year":"2024","unstructured":"Malhotra, K., Vasa, K.D., Chaudhary, N., et al.: A solution to graph coloring problem using genetic algorithm. EAI Endorsed Trans. Scalable Info. Syst. (2024). https:\/\/doi.org\/10.4108\/eetsis.5437","journal-title":"EAI Endorsed Trans. Scalable Info. Syst."},{"issue":"5","key":"781_CR36","doi-asserted-by":"publisher","first-page":"125","DOI":"10.9734\/AJRCOS\/2024\/v17i5443","volume":"17","author":"S Ogunkan","year":"2024","unstructured":"Ogunkan, S., Idowu, P., Omidiora, E., et al.: First fit algorithm: a graph coloring approach to conflict-free university course timetabling. Asian J. Res. Comput. Sci. 17(5), 125\u2013139 (2024). https:\/\/doi.org\/10.9734\/AJRCOS\/2024\/v17i5443","journal-title":"Asian J. Res. Comput. Sci."},{"key":"781_CR37","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1016\/j.neucom.2023.126631","volume":"2","author":"P Pardalos","year":"1998","unstructured":"Pardalos, P., Mavridou, T., Xue, J.: The graph coloring problem: a bibliographic survey. Handb. Comb. Optim. 2, 331\u2013395 (1998). https:\/\/doi.org\/10.1016\/j.neucom.2023.126631","journal-title":"Handb. Comb. Optim."},{"key":"781_CR38","doi-asserted-by":"publisher","unstructured":"Patidar, H., Chakrabarti, P.: A tree-based graph coloring algorithm using independent set. In: Progress in advanced computing and intelligent engineering: Proceedings of ICACIE 2017, 537\u2013546 (2019). https:\/\/doi.org\/10.1007\/978-981-13-0224-4_48","DOI":"10.1007\/978-981-13-0224-4_48"},{"key":"781_CR39","doi-asserted-by":"publisher","unstructured":"Rahman M.: Basic graph theory, 1st edn. Springer (2017) https:\/\/doi.org\/10.1007\/978-3-319-49475-3","DOI":"10.1007\/978-3-319-49475-3"},{"key":"781_CR40","doi-asserted-by":"publisher","unstructured":"Rajan A, Bhaiya D.: Accelerated kerninghan lin algorithm for graph partitioning. In: 2017 International conference on advances in computing, communications and informatics, India pp 58\u201366. (2017) https:\/\/doi.org\/10.1109\/ICACCI.2017.8125836","DOI":"10.1109\/ICACCI.2017.8125836"},{"issue":"1","key":"781_CR41","doi-asserted-by":"publisher","first-page":"64","DOI":"10.1109\/TCSS.2017.2762430","volume":"5","author":"S Roy","year":"2018","unstructured":"Roy, S., Dey, P., Kundu, D.: Social network analysis of cricket community using a composite distributed framework: from implementation viewpoint. IEEE Trans. Comput. Soc. Syst. 5(1), 64\u201381 (2018). https:\/\/doi.org\/10.1109\/TCSS.2017.2762430","journal-title":"IEEE Trans. Comput. Soc. Syst."},{"key":"781_CR42","doi-asserted-by":"publisher","unstructured":"Sakr S, Orakzai F, Abdelaziz I, et\u00a0al.: Large-Scale graph processing using Apache Giraph, 1st edn. Springer (2016) https:\/\/doi.org\/10.1007\/978-3-319-47431-1","DOI":"10.1007\/978-3-319-47431-1"},{"key":"781_CR43","doi-asserted-by":"publisher","unstructured":"Shao Y, Chen L, Cui B .: Efficient cohesive subgraphs detection in parallel. In: SIGMOD\u201914 Proceedings of the 2014 ACM SIGMOD international conference on management of data , Utah, USA pp 613\u2013624. (2014) https:\/\/doi.org\/10.1145\/2588555.2593665","DOI":"10.1145\/2588555.2593665"},{"key":"781_CR44","doi-asserted-by":"crossref","unstructured":"Shukla A, Garg M, Misra R.: An approach to solve graph coloring problem using linked list. IJASSR 4(2) (2019)","DOI":"10.21786\/bbrc\/12.2\/33"},{"key":"781_CR45","doi-asserted-by":"publisher","first-page":"10717","DOI":"10.1016\/j.asoc.2021.107174","volume":"104","author":"W Sun","year":"2021","unstructured":"Sun, W., Hao, J., Zang, Y., et al.: A solution-driven multilevel approach for graph coloring. Appl. Soft. Comput. 104, 10717 (2021). https:\/\/doi.org\/10.1016\/j.asoc.2021.107174","journal-title":"Appl. Soft. Comput."},{"issue":"1","key":"781_CR46","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1093\/comjnl\/10.1.85","volume":"10","author":"D Welsh","year":"1967","unstructured":"Welsh, D., Powell, M.: An upper bound for the chromatic number of a graph and its application to timetabling problems. Comput. J 10(1), 85\u201386 (1967). https:\/\/doi.org\/10.1093\/comjnl\/10.1.85","journal-title":"Comput. J"},{"issue":"1\u20133","key":"781_CR47","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1016\/0166-218X(94)90207-0","volume":"49","author":"D de Werra","year":"1994","unstructured":"de Werra, D., Gay, Y.: Chromatic scheduling and frequency assignment. Discrete Appl. Math. 49(1\u20133), 165\u2013174 (1994). https:\/\/doi.org\/10.1016\/0166-218X(94)90207-0","journal-title":"Discrete Appl. Math."},{"key":"781_CR48","doi-asserted-by":"publisher","unstructured":"Xin R, Gonzalez J, Franklin M, et\u00a0al .: Graphx: a resilient distributed graph system on spark. In: GRADES\u201913 1st International workshop on graph data management experiences and systems pp 1\u20136 . (2013) https:\/\/doi.org\/10.1145\/2484425.2484427","DOI":"10.1145\/2484425.2484427"},{"key":"781_CR49","doi-asserted-by":"publisher","first-page":"282","DOI":"10.1016\/j.cor.2014.05.017","volume":"51","author":"Z Zhou","year":"2014","unstructured":"Zhou, Z., Li, C., Huang, C., et al.: An exact algorithm with learning for the graph coloring problem. Comput. Oper. Res. 51, 282\u2013301 (2014). https:\/\/doi.org\/10.1016\/j.cor.2014.05.017","journal-title":"Comput. Oper. Res."}],"container-title":["International Journal of Parallel Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10766-024-00781-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10766-024-00781-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10766-024-00781-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,13]],"date-time":"2025-02-13T18:57:07Z","timestamp":1739473027000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10766-024-00781-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,10,17]]},"references-count":49,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2025,2]]}},"alternative-id":["781"],"URL":"https:\/\/doi.org\/10.1007\/s10766-024-00781-0","relation":{},"ISSN":["0885-7458","1573-7640"],"issn-type":[{"value":"0885-7458","type":"print"},{"value":"1573-7640","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,10,17]]},"assertion":[{"value":"9 April 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 October 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 October 2024","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors proclaim that they have no Conflict of interest as specified by Springer, or other interests that might be perceived to influence the results and\/or discussion reported in this manuscript.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}},{"value":"Ethical approval is not required, since this manuscript does not include any studies with human or animal subjects.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethical Approval"}}],"article-number":"1"}}