{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,3]],"date-time":"2026-01-03T06:51:00Z","timestamp":1767423060225,"version":"3.44.0"},"reference-count":40,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2025,9,1]],"date-time":"2025-09-01T00:00:00Z","timestamp":1756684800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,9,1]],"date-time":"2025-09-01T00:00:00Z","timestamp":1756684800000},"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":["62276060"],"award-info":[{"award-number":["62276060"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100015800","name":"Jilin Province Development and Reform Commission","doi-asserted-by":"publisher","award":["2019C053-9"],"award-info":[{"award-number":["2019C053-9"]}],"id":[{"id":"10.13039\/100015800","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2025,9]]},"DOI":"10.1007\/s10878-025-01338-8","type":"journal-article","created":{"date-parts":[[2025,9,9]],"date-time":"2025-09-09T10:38:29Z","timestamp":1757414309000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Graph Coloring problem solving using monte carlo tree search and deep reinforcement learning"],"prefix":"10.1007","volume":"50","author":[{"given":"Wenzhu","family":"Yang","sequence":"first","affiliation":[]},{"given":"Zhanshan","family":"Li","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,9,9]]},"reference":[{"key":"1338_CR1","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1111\/j.1475-3995.2009.00696.x","volume":"17","author":"E Malaguti","year":"2010","unstructured":"Malaguti E, Toth P (2010) A survey on vertex coloring problems. Int Trans Oper Res 17:1\u201334","journal-title":"Int Trans Oper Res"},{"key":"1338_CR2","doi-asserted-by":"publisher","first-page":"456","DOI":"10.1287\/mnsc.19.4.456","volume":"19","author":"J Randall Brown","year":"1972","unstructured":"Randall Brown J (1972) Chromatic scheduling and the chromatic number problem. Manage Sci 19:456\u2013463","journal-title":"Manage Sci"},{"key":"1338_CR3","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 MA (1996) A column generation approach for graph coloring. INFORMS J Comput 8:344\u2013354","journal-title":"INFORMS J Comput"},{"key":"1338_CR4","volume-title":"Object-oriented implementation of heuristic search methods for graph coloring, maximum clique, and satisfiability","author":"C Fleurent","year":"1993","unstructured":"Fleurent C, Ferland JA (1993) Object-oriented implementation of heuristic search methods for graph coloring, maximum clique, and satisfiability. Coloring, and Satisfiability, In Cliques"},{"key":"1338_CR5","first-page":"437","volume":"63","author":"C Fleurent","year":"1996","unstructured":"Fleurent C, Ferland JA (1996) Genetic and hybrid algorithms for graph coloring. INFORMS J Comput 63:437\u2013461","journal-title":"INFORMS J Comput"},{"key":"1338_CR6","doi-asserted-by":"crossref","unstructured":"Graves Alex. (2013) Abdelrahman Mohamed, and Geoffrey\u00a0E. Hinton. Speech recognition with deep recurrent neural networks. 2013 IEEE International Conference on Acoustics, Speech and Signal Processing, 6645\u20136649,","DOI":"10.1109\/ICASSP.2013.6638947"},{"key":"1338_CR7","doi-asserted-by":"publisher","first-page":"84","DOI":"10.1145\/3065386","volume":"60","author":"A Krizhevsky","year":"2012","unstructured":"Krizhevsky A, Sutskever I, Hinton GE (2012) Imagenet classification with deep convolutional neural networks. Commun ACM 60:84\u201390","journal-title":"Commun ACM"},{"key":"1338_CR8","doi-asserted-by":"crossref","unstructured":"Van Der Malsburg C (1986) Frank rosenblatt: Principles of neurodynamics: Perceptrons and the theory of brain mechanisms. In G\u00fcnther Palm and Ad\u00a0Aertsen, editors, Brain Theory, pages 245\u2013248, Berlin, Heidelberg, Springer Berlin Heidelberg","DOI":"10.1007\/978-3-642-70911-1_20"},{"key":"1338_CR9","doi-asserted-by":"publisher","first-page":"541","DOI":"10.1162\/neco.1989.1.4.541","volume":"1","author":"Y LeCun","year":"1989","unstructured":"LeCun Y, Boser BE, Denker JS (1989) Backpropagation applied to handwritten zip code recognition. Neural Comput 1:541\u2013551","journal-title":"Neural Comput"},{"key":"1338_CR10","doi-asserted-by":"crossref","unstructured":"Deng Jia, Dong Wei, Socher Richard, Li Li-Jia, Li K, Fei-Fei Li (2009) Imagenet: A large-scale hierarchical image database. 2009 IEEE Conference on Computer Vision and Pattern Recognition, 248\u2013255,","DOI":"10.1109\/CVPR.2009.5206848"},{"key":"1338_CR11","doi-asserted-by":"crossref","unstructured":"Watkins George, Montana G, Branke Juergen (2023) Generating a graph colouring heuristic with deep q-learning and graph neural networks. In Learning and Intelligent Optimization,","DOI":"10.1007\/978-3-031-44505-7_33"},{"key":"1338_CR12","doi-asserted-by":"crossref","unstructured":"Silver D, Schrittwieser J, Simonyan K, Antonoglou I, Huang A, Guez A, Hubert T, Lucas baker, Matthew Lai, Adrian Bolton, Yutian Chen, Timothy P. Lillicrap, Fan Hui, L. Sifre, George van den Driessche, Thore Graepel, and Demis Hassabis. (2017) Mastering the game of go without human knowledge. Nature 550:354\u2013359","DOI":"10.1038\/nature24270"},{"key":"1338_CR13","volume-title":"Heuristics: intelligent search strategies for computer problem solving","author":"J Pearl","year":"1984","unstructured":"Pearl J (1984) Heuristics: intelligent search strategies for computer problem solving. Addison-Wesley Longman Publishing Co., Inc, USA"},{"key":"1338_CR14","unstructured":"Altug B (2021) Solving graph coloring problem by using monte carlo tree search and artificial neural networks. https:\/\/github.com\/Bugraltug\/MCTS-GraphColoring,"},{"key":"1338_CR15","unstructured":"Khalil Elias\u00a0Boutros, Dai Hanjun, Zhang Yuyu, Dilkina Bistra\u00a0N, Song Le (2017) Learning combinatorial optimization algorithms over graphs. ArXiv:abs\/1704.01665"},{"key":"1338_CR16","unstructured":"Gualandi S, Chiarandini M (2019) Graph coloring benchmarks,"},{"key":"1338_CR17","doi-asserted-by":"crossref","unstructured":"Ignatiev Alexey, Morgado A, Marques-Silva Joao (2017) Cardinality encodings for graph optimization problems. In International Joint Conference on Artificial Intelligence,","DOI":"10.24963\/ijcai.2017\/91"},{"issue":"4","key":"1338_CR18","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1145\/359094.359101","volume":"22","author":"D Br\u00e9laz","year":"1979","unstructured":"Br\u00e9laz D (1979) New methods to color the vertices of a graph. Commun ACM 22(4):251\u2013256","journal-title":"Commun ACM"},{"key":"1338_CR19","doi-asserted-by":"crossref","unstructured":"Cazenave Tristan, Teytaud Fabien (2012) Application of the nested rollout policy adaptation algorithm to the traveling salesman problem with time windows. In Learning and Intelligent Optimization,","DOI":"10.1007\/978-3-642-34413-8_4"},{"key":"1338_CR20","doi-asserted-by":"crossref","unstructured":"Edelkamp Stefan, Gath Max, Cazenave Tristan, Teytaud Fabien (2013) Algorithm and knowledge engineering for the tsptw problem. 2013 IEEE Symposium on Computational Intelligence in Scheduling (CISched), pages 44\u201351,","DOI":"10.1109\/SCIS.2013.6613251"},{"key":"1338_CR21","unstructured":"Rosin Christopher\u00a0D (2011) Nested rollout policy adaptation for monte carlo tree search. Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, 649\u2013654,"},{"key":"1338_CR22","doi-asserted-by":"crossref","unstructured":"Edelkamp Stefan, Externest Eike, K\u00fchl Sebastian, Kuske Sabine (2021) Solving graph optimization problems in a framework for monte-carlo search. In Symposium on Combinatorial Search,","DOI":"10.1609\/socs.v8i1.18419"},{"key":"1338_CR23","doi-asserted-by":"crossref","unstructured":"Cazenave Tristan, Teytaud Olivier, Mark\u00a0H.M. (2021) Winands, editors. Monte Carlo Search: First Workshop, MCS 2020, Held in Conjunction with IJCAI 2020, Virtual Event, January 7, 2021, Proceedings. Communications in Computer and Information Science. Springer, Cham, Switzerland,","DOI":"10.1007\/978-3-030-89453-5"},{"key":"1338_CR24","doi-asserted-by":"crossref","unstructured":"Lemos Henrique, Prates Marcelo OR, Avelar Pedro HC, Lamb L (2019) Graph colouring meets deep learning: Effective graph neural network models for combinatorial problems. 2019 IEEE 31st International Conference on Tools with Artificial Intelligence (ICTAI), 879\u2013885,","DOI":"10.1109\/ICTAI.2019.00125"},{"key":"1338_CR25","doi-asserted-by":"publisher","first-page":"412","DOI":"10.1016\/j.eswa.2016.07.047","volume":"64","author":"Y Zhou","year":"2016","unstructured":"Zhou Y, Hao J-K, Duval B (2016) Reinforcement learning based local search for grouping problems: A case study on graph coloring. Expert Syst Appl 64:412\u2013422","journal-title":"Expert Syst Appl"},{"key":"1338_CR26","unstructured":"Gianinazzi Lukas, Fries M, Dryden Nikoli, Ben-Nun Tal, Besta Maciej, Hoefler Torsten (2021) Learning combinatorial node labeling algorithms. ArXiv:abs\/2106.03594"},{"key":"1338_CR27","unstructured":"Vaswani A, Shazeer NM, Parmar N, Uszkoreit J, Jones L, Gomez AN, Kaiser L, Polosukhin I (2017) Attention is all you need. In Neural Information Processing Systems"},{"key":"1338_CR28","unstructured":"Mnih Volodymyr, Kavukcuoglu Koray, Silver David, Graves Alex, Antonoglou Ioannis, Wierstra Daan, Riedmiller Martin\u00a0A. (2013) Playing atari with deep reinforcement learning. ArXiv:abs\/1312.5602"},{"key":"1338_CR29","doi-asserted-by":"crossref","unstructured":"Coulom R\u00e9mi. (2006) Efficient selectivity and backup operators in monte-carlo tree search. In Computers and Games,","DOI":"10.1007\/978-3-540-75538-8_7"},{"key":"1338_CR30","doi-asserted-by":"crossref","unstructured":"Kocsis L, Szepesvari C (2006) Bandit based monte-carlo planning. In European Conference on Machine Learning","DOI":"10.1007\/11871842_29"},{"key":"1338_CR31","unstructured":"Huang Jiayi, Patwary Md. Mostofa\u00a0Ali, Diamos Gregory\u00a0Frederick (2019) Coloring big graphs with alphagozero. ArXiv:abs\/1902.10162"},{"key":"1338_CR32","unstructured":"Howard RA (1960) Dynamic programming and Markov processes. Technology Press of Massachusetts Institute of Technology,"},{"key":"1338_CR33","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1109\/TCIAIG.2012.2186810","volume":"4","author":"C Browne","year":"2012","unstructured":"Browne C, Powley EJ, Whitehouse D, Lucas SMM, Cowling PI, Rohlfshagen P, Tavener S, Liebana DP, Samothrakis S, Colton S (2012) A survey of monte carlo tree search methods. IEEE Transactions on Computational Intelligence and AI in Games 4:1\u201343","journal-title":"IEEE Transactions on Computational Intelligence and AI in Games"},{"key":"1338_CR34","doi-asserted-by":"crossref","unstructured":"Frank Thomson Leighton (1979) A graph coloring algorithm for large scheduling problems. J Res Natl Bur Stand 84(6):489\u2013506","DOI":"10.6028\/jres.084.024"},{"key":"1338_CR35","unstructured":"Fricke GH, Hedetniemi Sandra\u00a0M, Hedetniemi Stephen\u00a0T, McRae AA, Wallis Charles\u00a0K, Jacobson Michael\u00a0S, Martin Harold\u00a0W, Weakley William\u00a0D (1995) Combinatorial problems on chessboards: A brief survey. In Graph Theory, Combinatorics, and Algorithms: Proceedings of the 7th Quadrennial International Conference on the Theory and Applications of Graphs, 1, 507\u2013528. New Jersey Institute of Technology,"},{"key":"1338_CR36","doi-asserted-by":"publisher","first-page":"290","DOI":"10.5486\/PMD.1959.6.3-4.12","volume":"6","author":"P Erdos","year":"2022","unstructured":"Erdos P, R\u00e9nyi A (2022) On random graphs. i. Publ Math Debrec 6:290\u2013297","journal-title":"Publ Math Debrec"},{"key":"1338_CR37","doi-asserted-by":"publisher","first-page":"440","DOI":"10.1038\/30918","volume":"393","author":"DJ Watts","year":"1998","unstructured":"Watts DJ, Strogatz SH (1998) Collective dynamics of \u2018small-world\u2019 networks. Nature 393:440\u2013442","journal-title":"Nature"},{"key":"1338_CR38","doi-asserted-by":"crossref","unstructured":"Albert Laszl\u00f3 Barab\u00e1si and R\u00e9ka Albert (1999) Emergence of scaling in random networks. Science 286(5439):509\u201312","DOI":"10.1126\/science.286.5439.509"},{"key":"1338_CR39","doi-asserted-by":"crossref","unstructured":"Brandes U, Gaertler M, Wagner D (2003) Experiments on graph clustering algorithms. In Embedded Systems and Applications","DOI":"10.1007\/978-3-540-39658-1_52"},{"key":"1338_CR40","unstructured":"Kingma Diederik\u00a0P, Ba Jimmy (2014) Adam: A method for stochastic optimization. CoRR arXiv:abs\/1412.6980"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-025-01338-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10878-025-01338-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-025-01338-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,28]],"date-time":"2025-09-28T04:55:20Z","timestamp":1759035320000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10878-025-01338-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,9]]},"references-count":40,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2025,9]]}},"alternative-id":["1338"],"URL":"https:\/\/doi.org\/10.1007\/s10878-025-01338-8","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"type":"print","value":"1382-6905"},{"type":"electronic","value":"1573-2886"}],"subject":[],"published":{"date-parts":[[2025,9]]},"assertion":[{"value":"17 July 2025","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 September 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"}}],"article-number":"20"}}