{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,11]],"date-time":"2025-09-11T20:31:02Z","timestamp":1757622662566,"version":"3.44.0"},"reference-count":43,"publisher":"Springer Science and Business Media LLC","issue":"12","license":[{"start":{"date-parts":[[2025,8,7]],"date-time":"2025-08-07T00:00:00Z","timestamp":1754524800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,8,7]],"date-time":"2025-08-07T00:00:00Z","timestamp":1754524800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["62206045","62106040","61976050"],"award-info":[{"award-number":["62206045","62106040","61976050"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100012226","name":"Fundamental Research Funds for the Central Universities","doi-asserted-by":"publisher","award":["2412022QD041","2412022ZD016"],"award-info":[{"award-number":["2412022QD041","2412022ZD016"]}],"id":[{"id":"10.13039\/501100012226","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100010211","name":"Education Department of Jilin Province","doi-asserted-by":"publisher","award":["JJKH20250335KJ"],"award-info":[{"award-number":["JJKH20250335KJ"]}],"id":[{"id":"10.13039\/501100010211","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100011789","name":"Department of Science and Technology of Jilin Province","doi-asserted-by":"publisher","award":["YDZJ202201ZYTS415"],"award-info":[{"award-number":["YDZJ202201ZYTS415"]}],"id":[{"id":"10.13039\/501100011789","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Jilin Science and Technology Association","award":["QT202320"],"award-info":[{"award-number":["QT202320"]}]},{"DOI":"10.13039\/501100011788","name":"Jilin Office of Philosophy and Social Science","doi-asserted-by":"publisher","award":["2023ZD15"],"award-info":[{"award-number":["2023ZD15"]}],"id":[{"id":"10.13039\/501100011788","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Supercomput"],"DOI":"10.1007\/s11227-025-07696-8","type":"journal-article","created":{"date-parts":[[2025,8,7]],"date-time":"2025-08-07T01:44:09Z","timestamp":1754531049000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["An incremental algorithm for dynamic graph coloring based on graph reduction and adaptive recoloring strategies"],"prefix":"10.1007","volume":"81","author":[{"given":"Yupeng","family":"Zhou","sequence":"first","affiliation":[]},{"given":"Hanhui","family":"Liu","sequence":"additional","affiliation":[]},{"given":"Xi","family":"Jin","sequence":"additional","affiliation":[]},{"given":"Yue","family":"Yin","sequence":"additional","affiliation":[]},{"given":"Shuli","family":"Hu","sequence":"additional","affiliation":[]},{"given":"Minghao","family":"Yin","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,8,7]]},"reference":[{"key":"7696_CR1","doi-asserted-by":"publisher","DOI":"10.7717\/peerj-cs.836","volume":"8","author":"SM Ardelean","year":"2022","unstructured":"Ardelean SM, Udrescu M (2022) Graph coloring using the reduced quantum genetic algorithm. PeerJ Computer Science 8:e836","journal-title":"PeerJ Computer Science"},{"key":"7696_CR2","doi-asserted-by":"crossref","unstructured":"Arnaout S, Rahman MA, Mowla MM, Hausman S, Korbel P (2024) Greedy graph coloring and hungarian algorithms for resource scheduling in twdm-pon. IEEE Access","DOI":"10.1109\/ACCESS.2024.3515483"},{"key":"7696_CR3","doi-asserted-by":"publisher","first-page":"1319","DOI":"10.1007\/s00453-018-0473-y","volume":"81","author":"L Barba","year":"2019","unstructured":"Barba L, Cardinal J, Korman M, Langerman S, Van Renssen A, Roeloffzen M, Verdonschot S (2019) Dynamic graph coloring. Algorithmica 81:1319\u20131341","journal-title":"Algorithmica"},{"key":"7696_CR4","doi-asserted-by":"crossref","unstructured":"Bhattacharya S, Chakrabarty D, Henzinger M, Nanongkai D (2018) Dynamic algorithms for graph coloring. In: Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, pp 1\u201320","DOI":"10.1137\/1.9781611975031.1"},{"key":"7696_CR5","unstructured":"Cai S, Lin J (2016) Fast solving maximum weight clique problem in massive graphs. In: IJCAI, pp 568\u2013574"},{"issue":"24","key":"7696_CR6","doi-asserted-by":"publisher","first-page":"15035","DOI":"10.1007\/s00500-021-06347-3","volume":"25","author":"D Chalupa","year":"2021","unstructured":"Chalupa D, Nielsen P (2021) Parameter-free and cooperative local search algorithms for graph colouring. Soft Comput 25(24):15035\u201315050","journal-title":"Soft Comput"},{"key":"7696_CR7","doi-asserted-by":"crossref","unstructured":"Chang L (2019) Efficient maximum clique computation over large sparse graphs. In: Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp 529\u2013538","DOI":"10.1145\/3292500.3330986"},{"key":"7696_CR8","doi-asserted-by":"publisher","unstructured":"Cremonezi BM, Vieira AB, Nacif JAM, Nogueira M (2017) A dynamic channel allocation protocol for medical environment under multiple base stations. In: 2017 IEEE Wireless Communications and Networking Conference (WCNC), pp 1\u20136, https:\/\/doi.org\/10.1109\/WCNC.2017.7925776","DOI":"10.1109\/WCNC.2017.7925776"},{"key":"7696_CR9","doi-asserted-by":"crossref","unstructured":"Das D, Ahmad SA, Kumar V (2020) Deep learning-based approximate graph-coloring algorithm for register allocation. In: 2020 IEEE\/ACM 6th Workshop on the LLVM Compiler Infrastructure in HPC (LLVM-HPC) and Workshop on Hierarchical Parallelism for Exascale Computing (HiPar), IEEE, pp 23\u201332","DOI":"10.1109\/LLVMHPCHiPar51896.2020.00008"},{"key":"7696_CR10","unstructured":"Dutot A, Guinand F, Olivier D, Pign\u00e9 Y (2007) On the decentralized dynamic graph coloring problem. Proc Worksh Compl Sys and Self-Org Mod"},{"issue":"200","key":"7696_CR11","doi-asserted-by":"publisher","first-page":"675","DOI":"10.1080\/01621459.1937.10503522","volume":"32","author":"M Friedman","year":"1937","unstructured":"Friedman M (1937) The use of ranks to avoid the assumption of normality implicit in the analysis of variance. J Am Stat Assoc 32(200):675\u2013701","journal-title":"J Am Stat Assoc"},{"key":"7696_CR12","unstructured":"Garcia S, Herrera F (2008) An extension on\" statistical comparisons of classifiers over multiple data sets\" for all pairwise comparisons. Journal of machine learning research 9(12)"},{"key":"7696_CR13","unstructured":"Guo J, Moalic L, Martin JN, Caminada A (2018) Exact graph coloring algorithms of getting partial and all best solutions. In: ISAIM"},{"key":"7696_CR14","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1007\/s10732-017-9327-z","volume":"24","author":"B Hardy","year":"2018","unstructured":"Hardy B, Lewis R, Thompson J (2018) Tackling the edge dynamic graph colouring problem with and without future adjacency information. Journal of Heuristics 24:321\u2013343","journal-title":"Journal of Heuristics"},{"key":"7696_CR15","doi-asserted-by":"crossref","unstructured":"Huang X, Cheng H, Qin L, Tian W, Yu JX (2014) Querying k-truss community in large and dynamic graphs. In: Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data, pp 1311\u20131322","DOI":"10.1145\/2588555.2610495"},{"key":"7696_CR16","doi-asserted-by":"crossref","unstructured":"Khanda A, Bhowmick S, Liang X, Das SK (2022) Parallel vertex color update on large dynamic networks. In: 2022 IEEE 29th International Conference on High Performance Computing, Data, and Analytics (HiPC), IEEE, pp 115\u2013124","DOI":"10.1109\/HiPC56025.2022.00027"},{"key":"7696_CR17","unstructured":"Kose A, Sonmez BA, Balaban M (2017) Simulated annealing algorithm for graph coloring. arXiv preprint arXiv:1712.00709"},{"key":"7696_CR18","doi-asserted-by":"publisher","unstructured":"Kumar\u00a0HS N, Chatterjee M (2015) Scheduling in dynamic spectrum access networks using graph coloring. In: 2015 International Conference on Advances in Computing, Communications and Informatics (ICACCI), pp 20\u20132https:\/\/doi.org\/10.1109\/ICACCI.2015.7275578","DOI":"10.1109\/ICACCI.2015.7275578"},{"key":"7696_CR19","doi-asserted-by":"crossref","unstructured":"Kunegis J (2013) Konect: the koblenz network collection. In: Proceedings of the 22nd International Conference on World Wide Web, pp 1343\u20131350","DOI":"10.1145\/2487788.2488173"},{"key":"7696_CR20","unstructured":"Leskovec J, Krevl A (2014) SNAP Datasets: Stanford large network dataset collection. http:\/\/snap.stanford.edu\/data"},{"issue":"4","key":"7696_CR21","doi-asserted-by":"publisher","first-page":"57","DOI":"10.22456\/2175-2745.80721","volume":"25","author":"AM de Lima","year":"2018","unstructured":"de Lima AM, Carmo R (2018) Exact algorithms for the graph coloring problem. Revista de Inform\u00e1tica Te\u00f3rica e Aplicada 25(4):57\u201373","journal-title":"Revista de Inform\u00e1tica Te\u00f3rica e Aplicada"},{"key":"7696_CR22","doi-asserted-by":"crossref","unstructured":"Lin J, Cai S, Luo C, Su K (2017) A reduction based method for coloring very large graphs. In: IJCAI, pp 517\u2013523","DOI":"10.24963\/ijcai.2017\/73"},{"issue":"8","key":"7696_CR23","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 (2006) An exact method for graph coloring. Computers & operations research 33(8):2189\u20132207","journal-title":"Computers & operations research"},{"issue":"2","key":"7696_CR24","doi-asserted-by":"publisher","first-page":"174","DOI":"10.1016\/j.disopt.2010.07.005","volume":"8","author":"E Malaguti","year":"2011","unstructured":"Malaguti E, Monaci M, Toth P (2011) An exact approach for the vertex coloring problem. Discret Optim 8(2):174\u2013190","journal-title":"Discret Optim"},{"key":"7696_CR25","doi-asserted-by":"crossref","unstructured":"Marappan R, Sethumadhavan G (2021) Solving graph coloring problem using divide and conquer-based turbulent particle swarm optimization. Arabian Journal for Science and Engineering pp 1\u201318","DOI":"10.1007\/s13369-021-06323-x"},{"key":"7696_CR26","unstructured":"Montgomery B (2001) Dynamic coloring of graphs. West Virginia University"},{"issue":"2","key":"7696_CR27","doi-asserted-by":"publisher","first-page":"117","DOI":"10.37745\/bjmas.2022.0158","volume":"4","author":"A Oke","year":"2023","unstructured":"Oke A, Wakili A, Olayiwola B (2023) Examination timetable scheduling using graph coloring for faculty of science. British Journal of Multidisciplinary and Advanced Studies 4(2):117\u2013143","journal-title":"British Journal of Multidisciplinary and Advanced Studies"},{"key":"7696_CR28","first-page":"1","volume-title":"2011 International Conference on Communications","author":"L Ouerfelli","year":"2011","unstructured":"Ouerfelli L, Bouziri H (2011) Greedy algorithms for dynamic graph coloring. 2011 International Conference on Communications. IEEE, Computing and Control Applications (CCCA), pp 1\u20135"},{"key":"7696_CR29","doi-asserted-by":"crossref","unstructured":"Porumbel DC, Hao JK, Kuntz P (2009) Position-guided tabu search algorithm for the graph coloring problem. In: International Conference on Learning and Intelligent Optimization, Springer, pp 148\u2013162","DOI":"10.1007\/978-3-642-11169-3_11"},{"key":"7696_CR30","unstructured":"Preuveneers D, Berbers Y (2004) Acodygra: an agent algorithm for coloring dynamic graphs. Symbolic and Numeric Algorithms for Scientific Computing 6:381\u2013390, 2004"},{"key":"7696_CR31","doi-asserted-by":"crossref","unstructured":"Sallinen S, Iwabuchi K, Poudel S, Gokhale M, Ripeanu M, Pearce R (2016) Graph colouring as a challenge problem for dynamic graph processing on distributed systems. In: SC\u201916: Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, IEEE, pp 347\u2013358","DOI":"10.1109\/SC.2016.29"},{"issue":"1","key":"7696_CR32","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1016\/j.ejor.2020.09.017","volume":"291","author":"O \u015eeker","year":"2021","unstructured":"\u015eeker O, Ekim T, Ta\u015fk\u0131n ZC (2021) An exact cutting plane algorithm to solve the selective graph coloring problem in perfect graphs. Eur J Oper Res 291(1):67\u201383","journal-title":"Eur J Oper Res"},{"key":"7696_CR33","doi-asserted-by":"crossref","unstructured":"Silard M, Fabian P, Papadopoulos GZ, Savelli P (2022) Frequency reuse in iab-based 5g networks using graph coloring methods. In: 2022 Global Information Infrastructure and Networking Symposium (GIIS), IEEE, pp 104\u2013110","DOI":"10.1109\/GIIS56506.2022.9937005"},{"key":"7696_CR34","doi-asserted-by":"crossref","unstructured":"Sipayung T, Suwilo S, Gultom P, et\u00a0al. (2022) Implementation of the greedy algorithm on graph coloring. In: Journal of Physics: Conference Series, IOP Publishing, vol 2157, p 012003","DOI":"10.1088\/1742-6596\/2157\/1\/012003"},{"issue":"3","key":"7696_CR35","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3392724","volume":"16","author":"S Solomon","year":"2020","unstructured":"Solomon S, Wein N (2020) Improved dynamic graph coloring. ACM Transactions on Algorithms (TALG) 16(3):1\u201324","journal-title":"ACM Transactions on Algorithms (TALG)"},{"key":"7696_CR36","doi-asserted-by":"crossref","unstructured":"Sudholt D, Zarges C (2010) Analysis of an iterated local search algorithm for vertex coloring. In: International Symposium on Algorithms and Computation, Springer, pp 340\u2013352","DOI":"10.1007\/978-3-642-17517-6_31"},{"issue":"1","key":"7696_CR37","doi-asserted-by":"publisher","first-page":"313","DOI":"10.7155\/jgaa.v28i1.2956","volume":"28","author":"M Theunis","year":"2024","unstructured":"Theunis M, Roeloffzen M (2024) Experimental analysis of algorithms for the dynamic graph coloring problem. Journal of Graph Algorithms and Applications 28(1):313\u2013349","journal-title":"Journal of Graph Algorithms and Applications"},{"key":"7696_CR38","doi-asserted-by":"crossref","unstructured":"TR P (2022) Analytical modeling on the coloring of certain graphs for applications of air traffic and air scheduling management. Aircr Eng Aerosp Technol 94(4):623\u2013632","DOI":"10.1108\/AEAT-04-2021-0104"},{"issue":"1","key":"7696_CR39","first-page":"63","volume":"21","author":"KJ Wu","year":"2020","unstructured":"Wu KJ, Hong YWP, Sheu JP (2020) Coloring-based channel allocation for multiple coexisting wireless body area networks: A game-theoretic approach. IEEE Trans Mob Comput 21(1):63\u201375","journal-title":"IEEE Trans Mob Comput"},{"issue":"3","key":"7696_CR40","doi-asserted-by":"publisher","first-page":"338","DOI":"10.14778\/3157794.3157802","volume":"11","author":"L Yuan","year":"2017","unstructured":"Yuan L, Qin L, Lin X, Chang L, Zhang W (2017) Effective and efficient dynamic graph coloring. Proceedings of the VLDB Endowment 11(3):338\u2013351","journal-title":"Proceedings of the VLDB Endowment"},{"issue":"2","key":"7696_CR41","first-page":"209","volume":"85","author":"S Zhou","year":"2023","unstructured":"Zhou S (2023) An algorithm for solving graph coloring problems based on an improved ant colony optimization. UPB Scientific Bulletin Series C 85(2):209\u2013220","journal-title":"UPB Scientific Bulletin Series C"},{"key":"7696_CR42","doi-asserted-by":"publisher","first-page":"542","DOI":"10.1016\/j.asoc.2018.01.027","volume":"65","author":"Y Zhou","year":"2018","unstructured":"Zhou Y, Duval B, Hao JK (2018) Improving probability learning based local search for graph coloring. Appl Soft Comput 65:542\u2013553","journal-title":"Appl Soft Comput"},{"key":"7696_CR43","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 CM, Huang C, Xu R (2014) An exact algorithm with learning for the graph coloring problem. Computers & operations research 51:282\u2013301","journal-title":"Computers & operations research"}],"container-title":["The Journal of Supercomputing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11227-025-07696-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11227-025-07696-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11227-025-07696-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,8]],"date-time":"2025-09-08T22:14:31Z","timestamp":1757369671000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11227-025-07696-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,8,7]]},"references-count":43,"journal-issue":{"issue":"12","published-online":{"date-parts":[[2025,8]]}},"alternative-id":["7696"],"URL":"https:\/\/doi.org\/10.1007\/s11227-025-07696-8","relation":{},"ISSN":["1573-0484"],"issn-type":[{"type":"electronic","value":"1573-0484"}],"subject":[],"published":{"date-parts":[[2025,8,7]]},"assertion":[{"value":"19 July 2025","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 August 2025","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}},{"value":"This material has not been published in whole or in part elsewhere. The manuscript is not currently being considered for publication in another journal. All authors have been personally and actively involved in substantive work leading to the manuscript, and will hold themselves jointly and individually responsible for its content.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethical approval"}},{"value":"Informed consent was obtained from all individual participants included in the study.","order":4,"name":"Ethics","group":{"name":"EthicsHeading","label":"Informed consent"}}],"article-number":"1217"}}