{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T02:32:07Z","timestamp":1760149927584,"version":"build-2065373602"},"reference-count":19,"publisher":"MDPI AG","issue":"10","license":[{"start":{"date-parts":[[2023,9,24]],"date-time":"2023-09-24T00:00:00Z","timestamp":1695513600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"National Natural Science Foundation","award":["62241206","Qiankehe Foundation-ZK[2022] General 550","KY[2019]201","KY[2021]282","[2019]QNSYXM-05","KY[2019]067","QNSY2018JS010","2023J01351","qnsy2019rc10","qnsyrc202203","qnsyrc202204","2019XK01ST","2020XK05ST","2019XK04ST","2021xjg029","S202210670024","61806050","IIS-2107213"],"award-info":[{"award-number":["62241206","Qiankehe Foundation-ZK[2022] General 550","KY[2019]201","KY[2021]282","[2019]QNSYXM-05","KY[2019]067","QNSY2018JS010","2023J01351","qnsy2019rc10","qnsyrc202203","qnsyrc202204","2019XK01ST","2020XK05ST","2019XK04ST","2021xjg029","S202210670024","61806050","IIS-2107213"]}]},{"DOI":"10.13039\/501100018555","name":"Science and Technology Plan Project of Guizhou Province","doi-asserted-by":"publisher","award":["62241206","Qiankehe Foundation-ZK[2022] General 550","KY[2019]201","KY[2021]282","[2019]QNSYXM-05","KY[2019]067","QNSY2018JS010","2023J01351","qnsy2019rc10","qnsyrc202203","qnsyrc202204","2019XK01ST","2020XK05ST","2019XK04ST","2021xjg029","S202210670024","61806050","IIS-2107213"],"award-info":[{"award-number":["62241206","Qiankehe Foundation-ZK[2022] General 550","KY[2019]201","KY[2021]282","[2019]QNSYXM-05","KY[2019]067","QNSY2018JS010","2023J01351","qnsy2019rc10","qnsyrc202203","qnsyrc202204","2019XK01ST","2020XK05ST","2019XK04ST","2021xjg029","S202210670024","61806050","IIS-2107213"]}],"id":[{"id":"10.13039\/501100018555","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Project for Growing Youth Talents of the Educational Department of Guizhou","award":["62241206","Qiankehe Foundation-ZK[2022] General 550","KY[2019]201","KY[2021]282","[2019]QNSYXM-05","KY[2019]067","QNSY2018JS010","2023J01351","qnsy2019rc10","qnsyrc202203","qnsyrc202204","2019XK01ST","2020XK05ST","2019XK04ST","2021xjg029","S202210670024","61806050","IIS-2107213"],"award-info":[{"award-number":["62241206","Qiankehe Foundation-ZK[2022] General 550","KY[2019]201","KY[2021]282","[2019]QNSYXM-05","KY[2019]067","QNSY2018JS010","2023J01351","qnsy2019rc10","qnsyrc202203","qnsyrc202204","2019XK01ST","2020XK05ST","2019XK04ST","2021xjg029","S202210670024","61806050","IIS-2107213"]}]},{"name":"Foundation Project for Talents of Qiannan Science and Technology Cooperation Platform Supported by the Department of Science and Technology, Guizhou","award":["62241206","Qiankehe Foundation-ZK[2022] General 550","KY[2019]201","KY[2021]282","[2019]QNSYXM-05","KY[2019]067","QNSY2018JS010","2023J01351","qnsy2019rc10","qnsyrc202203","qnsyrc202204","2019XK01ST","2020XK05ST","2019XK04ST","2021xjg029","S202210670024","61806050","IIS-2107213"],"award-info":[{"award-number":["62241206","Qiankehe Foundation-ZK[2022] General 550","KY[2019]201","KY[2021]282","[2019]QNSYXM-05","KY[2019]067","QNSY2018JS010","2023J01351","qnsy2019rc10","qnsyrc202203","qnsyrc202204","2019XK01ST","2020XK05ST","2019XK04ST","2021xjg029","S202210670024","61806050","IIS-2107213"]}]},{"name":"Educational Department of Guizhou","award":["62241206","Qiankehe Foundation-ZK[2022] General 550","KY[2019]201","KY[2021]282","[2019]QNSYXM-05","KY[2019]067","QNSY2018JS010","2023J01351","qnsy2019rc10","qnsyrc202203","qnsyrc202204","2019XK01ST","2020XK05ST","2019XK04ST","2021xjg029","S202210670024","61806050","IIS-2107213"],"award-info":[{"award-number":["62241206","Qiankehe Foundation-ZK[2022] General 550","KY[2019]201","KY[2021]282","[2019]QNSYXM-05","KY[2019]067","QNSY2018JS010","2023J01351","qnsy2019rc10","qnsyrc202203","qnsyrc202204","2019XK01ST","2020XK05ST","2019XK04ST","2021xjg029","S202210670024","61806050","IIS-2107213"]}]},{"name":"Foundation Project for Professors of Qiannan Normal University for Nationalities","award":["62241206","Qiankehe Foundation-ZK[2022] General 550","KY[2019]201","KY[2021]282","[2019]QNSYXM-05","KY[2019]067","QNSY2018JS010","2023J01351","qnsy2019rc10","qnsyrc202203","qnsyrc202204","2019XK01ST","2020XK05ST","2019XK04ST","2021xjg029","S202210670024","61806050","IIS-2107213"],"award-info":[{"award-number":["62241206","Qiankehe Foundation-ZK[2022] General 550","KY[2019]201","KY[2021]282","[2019]QNSYXM-05","KY[2019]067","QNSY2018JS010","2023J01351","qnsy2019rc10","qnsyrc202203","qnsyrc202204","2019XK01ST","2020XK05ST","2019XK04ST","2021xjg029","S202210670024","61806050","IIS-2107213"]}]},{"name":"Natural Science Foundation of Fujian","award":["62241206","Qiankehe Foundation-ZK[2022] General 550","KY[2019]201","KY[2021]282","[2019]QNSYXM-05","KY[2019]067","QNSY2018JS010","2023J01351","qnsy2019rc10","qnsyrc202203","qnsyrc202204","2019XK01ST","2020XK05ST","2019XK04ST","2021xjg029","S202210670024","61806050","IIS-2107213"],"award-info":[{"award-number":["62241206","Qiankehe Foundation-ZK[2022] General 550","KY[2019]201","KY[2021]282","[2019]QNSYXM-05","KY[2019]067","QNSY2018JS010","2023J01351","qnsy2019rc10","qnsyrc202203","qnsyrc202204","2019XK01ST","2020XK05ST","2019XK04ST","2021xjg029","S202210670024","61806050","IIS-2107213"]}]},{"name":"Special Foundation for Talents in Qiannan Normal University for Nationalities","award":["62241206","Qiankehe Foundation-ZK[2022] General 550","KY[2019]201","KY[2021]282","[2019]QNSYXM-05","KY[2019]067","QNSY2018JS010","2023J01351","qnsy2019rc10","qnsyrc202203","qnsyrc202204","2019XK01ST","2020XK05ST","2019XK04ST","2021xjg029","S202210670024","61806050","IIS-2107213"],"award-info":[{"award-number":["62241206","Qiankehe Foundation-ZK[2022] General 550","KY[2019]201","KY[2021]282","[2019]QNSYXM-05","KY[2019]067","QNSY2018JS010","2023J01351","qnsy2019rc10","qnsyrc202203","qnsyrc202204","2019XK01ST","2020XK05ST","2019XK04ST","2021xjg029","S202210670024","61806050","IIS-2107213"]}]},{"name":"Foundation Project of Science and Technology Plans of Qiannan","award":["62241206","Qiankehe Foundation-ZK[2022] General 550","KY[2019]201","KY[2021]282","[2019]QNSYXM-05","KY[2019]067","QNSY2018JS010","2023J01351","qnsy2019rc10","qnsyrc202203","qnsyrc202204","2019XK01ST","2020XK05ST","2019XK04ST","2021xjg029","S202210670024","61806050","IIS-2107213"],"award-info":[{"award-number":["62241206","Qiankehe Foundation-ZK[2022] General 550","KY[2019]201","KY[2021]282","[2019]QNSYXM-05","KY[2019]067","QNSY2018JS010","2023J01351","qnsy2019rc10","qnsyrc202203","qnsyrc202204","2019XK01ST","2020XK05ST","2019XK04ST","2021xjg029","S202210670024","61806050","IIS-2107213"]}]},{"name":"Nature Science Foundation of Qiannan","award":["62241206","Qiankehe Foundation-ZK[2022] General 550","KY[2019]201","KY[2021]282","[2019]QNSYXM-05","KY[2019]067","QNSY2018JS010","2023J01351","qnsy2019rc10","qnsyrc202203","qnsyrc202204","2019XK01ST","2020XK05ST","2019XK04ST","2021xjg029","S202210670024","61806050","IIS-2107213"],"award-info":[{"award-number":["62241206","Qiankehe Foundation-ZK[2022] General 550","KY[2019]201","KY[2021]282","[2019]QNSYXM-05","KY[2019]067","QNSY2018JS010","2023J01351","qnsy2019rc10","qnsyrc202203","qnsyrc202204","2019XK01ST","2020XK05ST","2019XK04ST","2021xjg029","S202210670024","61806050","IIS-2107213"]}]},{"name":"Education Quality Improvement Project of QNUN","award":["62241206","Qiankehe Foundation-ZK[2022] General 550","KY[2019]201","KY[2021]282","[2019]QNSYXM-05","KY[2019]067","QNSY2018JS010","2023J01351","qnsy2019rc10","qnsyrc202203","qnsyrc202204","2019XK01ST","2020XK05ST","2019XK04ST","2021xjg029","S202210670024","61806050","IIS-2107213"],"award-info":[{"award-number":["62241206","Qiankehe Foundation-ZK[2022] General 550","KY[2019]201","KY[2021]282","[2019]QNSYXM-05","KY[2019]067","QNSY2018JS010","2023J01351","qnsy2019rc10","qnsyrc202203","qnsyrc202204","2019XK01ST","2020XK05ST","2019XK04ST","2021xjg029","S202210670024","61806050","IIS-2107213"]}]},{"name":"National College Students\u2019 innovation and entrepreneurship training program","award":["62241206","Qiankehe Foundation-ZK[2022] General 550","KY[2019]201","KY[2021]282","[2019]QNSYXM-05","KY[2019]067","QNSY2018JS010","2023J01351","qnsy2019rc10","qnsyrc202203","qnsyrc202204","2019XK01ST","2020XK05ST","2019XK04ST","2021xjg029","S202210670024","61806050","IIS-2107213"],"award-info":[{"award-number":["62241206","Qiankehe Foundation-ZK[2022] General 550","KY[2019]201","KY[2021]282","[2019]QNSYXM-05","KY[2019]067","QNSY2018JS010","2023J01351","qnsy2019rc10","qnsyrc202203","qnsyrc202204","2019XK01ST","2020XK05ST","2019XK04ST","2021xjg029","S202210670024","61806050","IIS-2107213"]}]},{"DOI":"10.13039\/501100001809","name":"NSFC","doi-asserted-by":"publisher","award":["62241206","Qiankehe Foundation-ZK[2022] General 550","KY[2019]201","KY[2021]282","[2019]QNSYXM-05","KY[2019]067","QNSY2018JS010","2023J01351","qnsy2019rc10","qnsyrc202203","qnsyrc202204","2019XK01ST","2020XK05ST","2019XK04ST","2021xjg029","S202210670024","61806050","IIS-2107213"],"award-info":[{"award-number":["62241206","Qiankehe Foundation-ZK[2022] General 550","KY[2019]201","KY[2021]282","[2019]QNSYXM-05","KY[2019]067","QNSY2018JS010","2023J01351","qnsy2019rc10","qnsyrc202203","qnsyrc202204","2019XK01ST","2020XK05ST","2019XK04ST","2021xjg029","S202210670024","61806050","IIS-2107213"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["62241206","Qiankehe Foundation-ZK[2022] General 550","KY[2019]201","KY[2021]282","[2019]QNSYXM-05","KY[2019]067","QNSY2018JS010","2023J01351","qnsy2019rc10","qnsyrc202203","qnsyrc202204","2019XK01ST","2020XK05ST","2019XK04ST","2021xjg029","S202210670024","61806050","IIS-2107213"],"award-info":[{"award-number":["62241206","Qiankehe Foundation-ZK[2022] General 550","KY[2019]201","KY[2021]282","[2019]QNSYXM-05","KY[2019]067","QNSY2018JS010","2023J01351","qnsy2019rc10","qnsyrc202203","qnsyrc202204","2019XK01ST","2020XK05ST","2019XK04ST","2021xjg029","S202210670024","61806050","IIS-2107213"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Entropy"],"abstract":"<jats:p>The Minimum Vertex Weighted Coloring (MinVWC) problem is an important generalization of the classic Minimum Vertex Coloring (MinVC) problem which is NP-hard. Given a simple undirected graph G=(V,E), the MinVC problem is to find a coloring s.t. any pair of adjacent vertices are assigned different colors and the number of colors used is minimized. The MinVWC problem associates each vertex with a positive weight and defines the weight of a color to be the weight of its heaviest vertices, then the goal is the find a coloring that minimizes the sum of weights over all colors. Among various approaches, reduction is an effective one. It tries to obtain a subgraph whose optimal solutions can conveniently be extended into optimal ones for the whole graph, without costly branching. In this paper, we propose a reduction algorithm based on maximal clique enumeration. More specifically our algorithm utilizes a certain proportion of maximal cliques and obtains lower bounds in order to perform reductions. It alternates between clique sampling and graph reductions and consists of three successive procedures: promising clique reductions, better bound reductions and post reductions. Experimental results show that our algorithm returns considerably smaller subgraphs for numerous large benchmark graphs, compared to the most recent method named RedLS. Also, we evaluate individual impacts and some practical properties of our algorithm. Furthermore, we have a theorem which indicates that the reduction effects of our algorithm are equivalent to that of a counterpart which enumerates all maximal cliques in the whole graph if the run time is sufficiently long.<\/jats:p>","DOI":"10.3390\/e25101376","type":"journal-article","created":{"date-parts":[[2023,9,24]],"date-time":"2023-09-24T10:36:26Z","timestamp":1695551786000},"page":"1376","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Iterated Clique Reductions in Vertex Weighted Coloring for Large Sparse Graphs"],"prefix":"10.3390","volume":"25","author":[{"given":"Yi","family":"Fan","sequence":"first","affiliation":[{"name":"School of Mathematics and Statistic, Qiannan Normal University for Nationalities, Duyun 558000, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zaijun","family":"Zhang","sequence":"additional","affiliation":[{"name":"School of Mathematics and Statistic, Qiannan Normal University for Nationalities, Duyun 558000, China"},{"name":"Key Laboratory of Complex Systems and Intelligent Optimization of Guizhou Province, Duyun 558000, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Quan","family":"Yu","sequence":"additional","affiliation":[{"name":"School of Mathematics and Statistic, Qiannan Normal University for Nationalities, Duyun 558000, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yongxuan","family":"Lai","sequence":"additional","affiliation":[{"name":"School of Mathematics and Information Engineering, Longyan University, Longyan 364000, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6741-9699","authenticated-orcid":false,"given":"Kaile","family":"Su","sequence":"additional","affiliation":[{"name":"Institute for Integrated and Intelligent Systems, Griffith University, Brisbane, QLD 4111, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yiyuan","family":"Wang","sequence":"additional","affiliation":[{"name":"School of Computer Science and Information Technology, Northeast Normal University, Changchun 130024, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shiwei","family":"Pan","sequence":"additional","affiliation":[{"name":"School of Computer Science and Information Technology, Northeast Normal University, Changchun 130024, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5102-8244","authenticated-orcid":false,"given":"Longin Jan","family":"Latecki","sequence":"additional","affiliation":[{"name":"Department of Computer and Information Sciences, Temple University, Philadelphia, PA 19122, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2023,9,24]]},"reference":[{"key":"ref_1","unstructured":"Garey, M.R., and Johnson, D.S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"101","DOI":"10.1007\/s10288-008-0071-y","article-title":"The Vertex Coloring Problem and its generalizations","volume":"7","author":"Malaguti","year":"2009","journal-title":"4OR"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"232","DOI":"10.1016\/0377-2217(89)90389-5","article-title":"An optimal column-generation-with-ranking algorithm for very large scale set partitioning problems in traffic assignment","volume":"41","author":"Ribeiro","year":"1989","journal-title":"Eur. J. Oper. Res."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"164","DOI":"10.1287\/ijoc.12.3.164.12639","article-title":"Reactive GRASP: An Application to a Matrix Decomposition Problem in TDMA Traffic Assignment","volume":"12","author":"Prais","year":"1998","journal-title":"Informs J. Comput."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"603","DOI":"10.1016\/S1474-6670(17)39472-7","article-title":"Graph Partitioning and Set Covering for the Optimal Design of a Production System in the Metal Industry","volume":"33","author":"Gavranovic","year":"2000","journal-title":"IFAC Proc. Vol."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"874","DOI":"10.1287\/opre.45.6.874","article-title":"Scheduling Semiconductor Burn-In Operations to Minimize Total Flowtime","volume":"45","author":"Hochbaum","year":"1997","journal-title":"Oper. Res."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"130","DOI":"10.1016\/j.disopt.2012.03.002","article-title":"Exact weighted vertex coloring via branch-and-price","volume":"9","author":"Furini","year":"2012","journal-title":"Discret. Optim."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1016\/j.dam.2016.09.018","article-title":"Solving vertex coloring problems as maximum weight stable set problems","volume":"217","author":"Cornaz","year":"2017","journal-title":"Discret. Appl. Math."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"503","DOI":"10.1007\/s10732-008-9075-1","article-title":"Models and heuristic algorithms for a weighted vertex coloring problem","volume":"15","author":"Malaguti","year":"2009","journal-title":"J. Heuristics"},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1016\/j.ins.2018.07.037","article-title":"Adaptive feasible and infeasible tabu search for weighted vertex coloring","volume":"466","author":"Sun","year":"2018","journal-title":"Inf. Sci."},{"key":"ref_11","first-page":"2433","article-title":"Reduction and Local Search for Weighted Graph Coloring Problem","volume":"34","author":"Wang","year":"2020","journal-title":"Proc. AAAI Conf. Artif. Intell."},{"key":"ref_12","unstructured":"Cai, S., and Lin, J. (2016, January 9\u201315). Fast Solving Maximum Weight Clique Problem in Massive Graphs. Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, IJCAI 2016, New York, NY, USA."},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Fan, Y., Li, N., Li, C., Ma, Z., Latecki, L.J., and Su, K. (2017, January 19\u201325). Restart and Random Walk in Local Search for Maximum Vertex Weight Cliques with Evaluations in Clustering Aggregation. Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, IJCAI 2017, Melbourne, Australia.","DOI":"10.24963\/ijcai.2017\/87"},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"3966","DOI":"10.1109\/TSMC.2023.3240992","article-title":"EIDLS: An Edge-Intelligence-Based Distributed Learning System Over Internet of Things","volume":"53","author":"Wang","year":"2023","journal-title":"IEEE Trans. Syst. Man Cybern. Syst."},{"key":"ref_15","first-page":"1","article-title":"Edge Computing and Sensor-Cloud: Overview, Solutions, and Directions","volume":"55","author":"Wang","year":"2023","journal-title":"ACM Comput. Surv."},{"key":"ref_16","unstructured":"Eubank, S., Kumar, V.S.A., Marathe, M., Srinivasan, A., and Wang, N. (2004, January 11\u201314). Structural and algorithmic aspects of large social networks. Proceedings of the Fifteenth Acm-Siam Symposium on Discrete Algorithms, New Orleans, LA, USA."},{"key":"ref_17","unstructured":"Fan, C., and Lu, L. (2006). Complex Graphs and Networks, American Mathematical Society."},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Fan, Y., Li, C., Ma, Z., Wen, L., Sattar, A., and Su, K. (2016, January 5\u20138). Local Search for Maximum Vertex Weight Clique on Large Sparse Graphs with Efficient Data Structures. Proceedings of the Twenty-Nineth Australasian Joint Conference, AI 2016, Hobart, TAS, Australia.","DOI":"10.1007\/978-3-319-50127-7_21"},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Fan, Y., Lai, Y., Li, C., Li, N., Ma, Z., Zhou, J., Latecki, L.J., and Su, K. (2019, January 22\u201325). Efficient Local Search for Minimum Dominating Sets in Large Graphs. Proceedings of the Twenty-Fourth International Conference on Database Systems for Advanced Applications, DASFAA 2019, Chiang Mai, Thailand.","DOI":"10.1007\/978-3-030-18579-4_13"}],"container-title":["Entropy"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1099-4300\/25\/10\/1376\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T20:57:10Z","timestamp":1760129830000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1099-4300\/25\/10\/1376"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,9,24]]},"references-count":19,"journal-issue":{"issue":"10","published-online":{"date-parts":[[2023,10]]}},"alternative-id":["e25101376"],"URL":"https:\/\/doi.org\/10.3390\/e25101376","relation":{},"ISSN":["1099-4300"],"issn-type":[{"type":"electronic","value":"1099-4300"}],"subject":[],"published":{"date-parts":[[2023,9,24]]}}}