{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,16]],"date-time":"2025-09-16T16:31:32Z","timestamp":1758040292487,"version":"3.44.0"},"reference-count":45,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2025,7,7]],"date-time":"2025-07-07T00:00:00Z","timestamp":1751846400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,7,7]],"date-time":"2025-07-07T00:00:00Z","timestamp":1751846400000},"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":["Nos.62106040","Nos.62206045"],"award-info":[{"award-number":["Nos.62106040","Nos.62206045"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Jilin Province Science and Technology Department Project","award":["Nos. YDZJ202201ZYTS415","Nos.YDZJ202201ZYTS413"],"award-info":[{"award-number":["Nos. YDZJ202201ZYTS415","Nos.YDZJ202201ZYTS413"]}]},{"name":"Jilin Education Department Project","award":["Nos. JJKH20231319KJ","Nos.JJKH20240201KJ"],"award-info":[{"award-number":["Nos. JJKH20231319KJ","Nos.JJKH20240201KJ"]}]},{"name":"Jilin Science and Technology Association","award":["Nos. QT202320","Nos.QT202112"],"award-info":[{"award-number":["Nos. QT202320","Nos.QT202112"]}]},{"name":"the Fundamental Research Funds for the Central Universities","award":["No.2412022ZD016"],"award-info":[{"award-number":["No.2412022ZD016"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Memetic Comp."],"published-print":{"date-parts":[[2025,9]]},"DOI":"10.1007\/s12293-025-00470-6","type":"journal-article","created":{"date-parts":[[2025,7,7]],"date-time":"2025-07-07T07:29:55Z","timestamp":1751873395000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["A Multi-start Algorithm with Iterated Decremental Local Search for Minimum Capacitated Dominating Set Problem in Large Graphs"],"prefix":"10.1007","volume":"17","author":[{"given":"Shuli","family":"Hu","sequence":"first","affiliation":[]},{"given":"Shuang","family":"Zhou","sequence":"additional","affiliation":[]},{"given":"Dian","family":"Ling","sequence":"additional","affiliation":[]},{"given":"Jiaqi","family":"Li","sequence":"additional","affiliation":[]},{"given":"Ruizhi","family":"Li","sequence":"additional","affiliation":[]},{"given":"Yupeng","family":"Zhou","sequence":"additional","affiliation":[]},{"given":"Minghao","family":"Yin","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,7,7]]},"reference":[{"key":"470_CR1","doi-asserted-by":"crossref","unstructured":"Jie W, Li H (1999) On calculating connected dominating set for efficient routing in ad hoc wireless networks. In: International workshop on discrete algorithms & methods for mobile computing & communications, pp. 7\u201314","DOI":"10.1145\/313239.313261"},{"issue":"4","key":"470_CR2","doi-asserted-by":"publisher","first-page":"461","DOI":"10.1007\/s00453-001-0116-5","volume":"33","author":"Alber","year":"2002","unstructured":"Alber, Bodlaender, Fernau, Kloks, Niedermeier (2002) Fixed parameter algorithms for dominating set and related problems on planar graphs. Algorithmica 33(4):461\u2013493","journal-title":"Algorithmica"},{"key":"470_CR3","unstructured":"Fei D, Jie W (2005) On constructing k-connected k-dominating set in wireless networks. In: IEEE international parallel & distributed processing symposium"},{"issue":"10","key":"470_CR4","doi-asserted-by":"publisher","first-page":"908","DOI":"10.1109\/TPDS.2004.48","volume":"15","author":"D Fei","year":"2004","unstructured":"Fei D, Jie W (2004) An extended localized algorithm for connected dominating set formation in ad hoc wireless networks. IEEE Trans Parallel Distrib Syst 15(10):908\u2013920","journal-title":"IEEE Trans Parallel Distrib Syst"},{"issue":"2","key":"470_CR5","first-page":"162","volume":"6","author":"K Erciyes","year":"2008","unstructured":"Erciyes K, Dagdeviren O, Cokuslu D, Ozsoyeller D (2008) Graph theoretic clustering algorithms in mobile ad hoc networks and wireless sensor networks survey. Appl Math Comput 6(2):162\u2013180","journal-title":"Appl Math Comput"},{"key":"470_CR6","doi-asserted-by":"crossref","unstructured":"Lawrie D, Croft WB, Rosenberg AL (2001) Finding topic words for hierarchical summarization. In: International Acm Sigir conference on research & development in information retrieval, pp. 349\u2013357","DOI":"10.1145\/383952.384022"},{"key":"470_CR7","unstructured":"Chao S, Tao L (2010) Multi-document summarization via the minimum dominating set. In: International conference on computational linguistics, pp. 984\u2013992"},{"key":"470_CR8","doi-asserted-by":"crossref","unstructured":"Kao-Mong J, Han-lin C (2010) Approximation algorithms for the capacitated domination problem. In: International workshop on frontiers in algorithmics Springer, pp. 296\u2013306","DOI":"10.1007\/978-3-642-14553-7_19"},{"issue":"13","key":"470_CR9","doi-asserted-by":"publisher","first-page":"22","DOI":"10.1016\/j.swevo.2013.06.002","volume":"13","author":"A Potluri","year":"2013","unstructured":"Potluri A, Singh A (2013) Metaheuristic algorithms for computing capacitated dominating set with uniform and variable capacities. Swarm Evol Comput 13(13):22\u201333","journal-title":"Swarm Evol Comput"},{"key":"470_CR10","volume-title":"Computers and intractability: A guide to the theory of np-completeness","author":"MR Garey","year":"1983","unstructured":"Garey MR, Johnson DS (1983) Computers and intractability: A guide to the theory of np-completeness. W. H. Freeman, New York"},{"key":"470_CR11","doi-asserted-by":"crossref","unstructured":"Hedar A-R, Ismail R (2010) Hybrid genetic algorithm for minimum dominating set problem. In: Computational Science and Its Applications\u2013ICCSA 2010: International Conference, Fukuoka, Japan, March 23-26, 2010, Proceedings, Part IV 10, pp. 457\u2013467. Springer","DOI":"10.1007\/978-3-642-12189-0_40"},{"issue":"10","key":"470_CR12","doi-asserted-by":"publisher","first-page":"881","DOI":"10.1080\/08839510600940132","volume":"20","author":"C Ho","year":"2006","unstructured":"Ho C, Singh Y, Ewe H (2006) An enhanced ant colony optimiztion metaheuristic for the minium dominating set problem. Appl Artif Intell 20(10):881\u2013903","journal-title":"Appl Artif Intell"},{"issue":"4","key":"470_CR13","doi-asserted-by":"publisher","first-page":"1173","DOI":"10.1007\/s10878-013-9690-0","volume":"30","author":"YL Du","year":"2015","unstructured":"Du YL, Du HW (2015) A new bound on maximum independent set and minimum connected dominating set in unit disk graphs. J Comb Optim 30(4):1173\u20131179","journal-title":"J Comb Optim"},{"issue":"5","key":"470_CR14","doi-asserted-by":"publisher","first-page":"1154","DOI":"10.1007\/s10955-015-1220-2","volume":"159","author":"JH Zhao","year":"2015","unstructured":"Zhao JH, Habibulla Y, Zhou HJ (2015) Statistical mechanics of the minimum dominating set problem. J Stat Phys 159(5):1154\u20131174","journal-title":"J Stat Phys"},{"key":"470_CR15","doi-asserted-by":"crossref","unstructured":"Li R, Hu S, Jian G, Zhou Y, Wang Y, Yin M (2016) Grasp for connected dominating set problems. Neural Comput Appl, 1\u20139","DOI":"10.1007\/s00521-016-2429-y"},{"issue":"1","key":"470_CR16","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.tcs.2005.08.037","volume":"352","author":"W Wu","year":"2006","unstructured":"Wu W, Du H, Jia X, Li Y, Huang CH (2006) Minimum connected dominating sets and maximal independent sets in unit disk graphs. Theoret Comput Sci 352(1):1\u20137","journal-title":"Theoret Comput Sci"},{"issue":"12","key":"470_CR17","doi-asserted-by":"publisher","first-page":"4695","DOI":"10.1016\/j.asoc.2013.07.014","volume":"13","author":"S Sundar","year":"2013","unstructured":"Sundar S, Singh A (2013) New heuristic approaches for the dominating tree problem. Appl Soft Comput J 13(12):4695\u20134703","journal-title":"Appl Soft Comput J"},{"key":"470_CR18","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1006\/jagm.1993.1047","volume":"15","author":"J Bar-Ilan","year":"1993","unstructured":"Bar-Ilan J, Kortsarz G, Peleg D (1993) How to allocate network centers. J Algorithms 15:385\u2013415","journal-title":"J Algorithms"},{"issue":"4","key":"470_CR19","doi-asserted-by":"publisher","first-page":"811","DOI":"10.1007\/s00224-010-9271-x","volume":"47","author":"F Kuhn","year":"2010","unstructured":"Kuhn F, Moscibroda T (2010) Distributed approximation of capacitated dominating sets. Theory Comput Syst 47(4):811\u2013836","journal-title":"Theory Comput Syst"},{"key":"470_CR20","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1016\/j.dam.2012.10.021","volume":"168","author":"M Liedloff","year":"2014","unstructured":"Liedloff M, Todinca I, Villanger Y (2014) Solving capacitated dominating set by using covering by subsets and maximum matching. Discret Appl Math 168:60\u201368","journal-title":"Discret Appl Math"},{"key":"470_CR21","doi-asserted-by":"crossref","unstructured":"Bodlaender HL, Lokshtanov D, Penninkx E (2009) Planar capacitated dominating set is w [1]-hard. In: Parameterized and Exact Computation: 4th International Workshop, IWPEC 2009, Copenhagen, Denmark, September 10-11, 2009, Revised Selected Papers 4, pp. 50\u201360. Springer","DOI":"10.1007\/978-3-642-11269-0_4"},{"key":"470_CR22","doi-asserted-by":"crossref","unstructured":"Becker A (2018) Capacitated dominating set on planar graphs. In: International Workshop on Approximation and Online Algorithms, pp. 1\u201316","DOI":"10.1007\/978-3-319-89441-6_1"},{"key":"470_CR23","doi-asserted-by":"crossref","unstructured":"Potluri A, Singh A (2012) A greedy heuristic and its variants for minimum capacitated dominating set. In: International Conference on Contemporary Computing, pp. 28\u201339","DOI":"10.1007\/978-3-642-32129-0_9"},{"issue":"6","key":"470_CR24","doi-asserted-by":"publisher","first-page":"849","DOI":"10.1057\/s41274-017-0268-6","volume":"69","author":"R Li","year":"2018","unstructured":"Li R, Hu S, Zhao P, Zhou Y, Yin M (2018) A novel local search algorithm for the minimum capacitated dominating set. J Oper Res Soc 69(6):849\u2013863","journal-title":"J Oper Res Soc"},{"key":"470_CR25","doi-asserted-by":"crossref","unstructured":"Pinacho-Davidson P, Bouamama S, Blum C (2019) Application of cmsa to the minimum capacitated dominating set problem. In: Proceedings of the Genetic and Evolutionary Computation Conference, pp. 321\u2013328","DOI":"10.1145\/3321707.3321807"},{"issue":"11","key":"470_CR26","doi-asserted-by":"publisher","first-page":"1858","DOI":"10.3390\/math8111858","volume":"8","author":"P Pinacho-Davidson","year":"2020","unstructured":"Pinacho-Davidson P, Blum C (2020) Barrakuda: A hybrid evolutionary algorithm for minimum capacitated dominating set problem. Mathematics 8(11):1858","journal-title":"Mathematics"},{"key":"470_CR27","doi-asserted-by":"publisher","DOI":"10.1016\/j.asoc.2021.107437","volume":"108","author":"MR Nakkala","year":"2021","unstructured":"Nakkala MR, Singh A, Rossi A (2021) Multi-start iterated local search, exact and matheuristic approaches for minimum capacitated dominating set problem. Appl Soft Comput 108:107437","journal-title":"Appl Soft Comput"},{"key":"470_CR28","doi-asserted-by":"publisher","first-page":"64","DOI":"10.1016\/j.ins.2018.08.052","volume":"471","author":"S Cai","year":"2019","unstructured":"Cai S, Li Y, Hou W, Wang H (2019) Towards faster local search for minimum weight vertex cover on massive graphs. Inf Sci 471:64\u201379","journal-title":"Inf Sci"},{"key":"470_CR29","doi-asserted-by":"crossref","unstructured":"Chen J, Wang Y, Xu W, Ji J, Yin M (2023) Improved local search for the minimum weight dominating set problem in massive graphs by using a deep optimization mechanism. Artif Intell, 64\u201379","DOI":"10.1016\/j.artint.2022.103819"},{"key":"470_CR30","unstructured":"Morris P (1993) The breakout method for escaping from local minima. In: Proceedings of the 11th National Conference on Artificial Intelligence. Washington, DC, USA, July 11-15, 1993., pp. 40\u201345"},{"key":"470_CR31","doi-asserted-by":"publisher","first-page":"687","DOI":"10.1613\/jair.3907","volume":"46","author":"S Cai","year":"2013","unstructured":"Cai S, Su K, Luo C, Sattar A (2013) Numvc: An efficient local search algorithm for minimum vertex cover. J Artif Intell Res 46:687\u2013716","journal-title":"J Artif Intell Res"},{"issue":"3","key":"470_CR32","doi-asserted-by":"publisher","first-page":"900","DOI":"10.1016\/j.cor.2005.05.017","volume":"34","author":"G Br\u00f8nmo","year":"2007","unstructured":"Br\u00f8nmo G, Christiansen M, Fagerholt K, Nygreen B (2007) A multi-start local search heuristic for ship scheduling-a computational study. Comput Oper Res 34(3):900\u2013917","journal-title":"Comput Oper Res"},{"issue":"5","key":"470_CR33","first-page":"1028","volume":"45","author":"C Luo","year":"2017","unstructured":"Luo C, Cai S, Su K, Wu W (2017) Clause states based configuration checking in local search for satisfiability. IEEE Trans Cybern 45(5):1028\u20131041","journal-title":"IEEE Trans Cybern"},{"key":"470_CR34","doi-asserted-by":"crossref","unstructured":"Wang Y, Cai S, Yin M (2017) Local search for minimum weight dominating set with two-level configuration checking and frequency based scoring function. J Artif Intell Res 58:267\u2013295","DOI":"10.1613\/jair.5205"},{"key":"470_CR35","doi-asserted-by":"publisher","first-page":"481","DOI":"10.1007\/978-3-642-40627-0_37","volume":"8124","author":"C Luo","year":"2013","unstructured":"Luo C, Cai S, Wei W, Su K (2013) Focused random walk with configuration checking and break minimum for satisfiability. Lect Notes Comput Sci 8124:481\u2013496","journal-title":"Lect Notes Comput Sci"},{"issue":"9","key":"470_CR36","doi-asserted-by":"publisher","first-page":"1672","DOI":"10.1016\/j.artint.2011.03.003","volume":"175","author":"S Cai","year":"2011","unstructured":"Cai S, Su K, Sattar A (2011) Local search with edge weighting and configuration checking heuristics for minimum vertex cover. Artif Intell 175(9):1672\u20131696","journal-title":"Artif Intell"},{"key":"470_CR37","doi-asserted-by":"crossref","unstructured":"Li R, Cai S, Hu S, Yin M, Gao J (2018) A novel local search for minimum weighted vertex cover problem. In: Twenty-Second AAAI Conference on Artificial Intelligence, pp. 8107\u20138108","DOI":"10.1609\/aaai.v32i1.12137"},{"key":"470_CR38","doi-asserted-by":"crossref","unstructured":"Wang Y, Cai S, Chen J, Yin M (2018) A fast local search algorithm for minimum weight dominating set problem on massive graphs. In: International Joint Conference on Artificial Intelligence 2018, pp. 1514\u20131522","DOI":"10.24963\/ijcai.2018\/210"},{"key":"470_CR39","doi-asserted-by":"crossref","unstructured":"Ma Z, Fan Y, Su K, Li C, Sattar A (2016) Local search with noisy strategy for minimum vertex cover in massive graphs. In: PRICAI 2016: Trends in Artificial Intelligence: 14th Pacific Rim International Conference on Artificial Intelligence, Phuket, Thailand, August 22-26, 2016, Proceedings 14, pp. 283\u2013294. Springer","DOI":"10.1007\/978-3-319-42911-3_24"},{"key":"470_CR40","doi-asserted-by":"publisher","first-page":"64","DOI":"10.1016\/j.ins.2018.08.052","volume":"471","author":"S Cai","year":"2019","unstructured":"Cai S, Li Y, Hou W, Wang H (2019) Towards faster local search for minimum weight vertex cover on massive graphs. Inf Sci 471:64\u201379","journal-title":"Inf Sci"},{"key":"470_CR41","doi-asserted-by":"crossref","unstructured":"Rossi R, Ahmed N (2015) The network data repository with interactive graph analytics and visualization. In: Twenty-Ninth AAAI Conference on Artificial Intelligence, pp. 4292\u20134293","DOI":"10.1609\/aaai.v29i1.9277"},{"key":"470_CR42","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1016\/j.orp.2016.09.002","volume":"3","author":"M L\u00f3pez-Ib\u00e1\u00f1ez","year":"2016","unstructured":"L\u00f3pez-Ib\u00e1\u00f1ez M, Dubois-Lacoste J, P\u00e9rez C\u00e1ceres L, St\u00fctzle T, Birattari M (2016) The irace package: Iterated racing for automatic algorithm configuration. Oper Res Perspect 3:43\u201358. https:\/\/doi.org\/10.1016\/j.orp.2016.09.002","journal-title":"Oper Res Perspect"},{"issue":"2019","key":"470_CR43","first-page":"9","volume":"27","author":"T Pohlert","year":"2014","unstructured":"Pohlert T (2014) The pairwise multiple comparison of mean ranks package (pmcmr). R package 27(2019):9","journal-title":"R package"},{"key":"470_CR44","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1007\/s12293-016-0216-z","volume":"10","author":"S Hu","year":"2018","unstructured":"Hu S, Li R, Zhao P, Yin M (2018) A hybrid metaheuristic algorithm for generalized vertex cover problem. Memetic Computing 10:165\u2013176","journal-title":"Memetic Computing"},{"issue":"C","key":"470_CR45","doi-asserted-by":"publisher","first-page":"428","DOI":"10.1016\/j.ins.2016.08.053","volume":"372","author":"R Li","year":"2016","unstructured":"Li R, Hu S, Zhang H, Yin M (2016) An efficient local search framework for the minimum weighted vertex cover problem. Inf Sci 372(C):428\u2013445","journal-title":"Inf Sci"}],"container-title":["Memetic Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s12293-025-00470-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s12293-025-00470-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s12293-025-00470-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,11]],"date-time":"2025-09-11T06:54:37Z","timestamp":1757573677000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s12293-025-00470-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,7,7]]},"references-count":45,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2025,9]]}},"alternative-id":["470"],"URL":"https:\/\/doi.org\/10.1007\/s12293-025-00470-6","relation":{},"ISSN":["1865-9284","1865-9292"],"issn-type":[{"type":"print","value":"1865-9284"},{"type":"electronic","value":"1865-9292"}],"subject":[],"published":{"date-parts":[[2025,7,7]]},"assertion":[{"value":"13 June 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 June 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 July 2025","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 declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}},{"value":"The data used in this work does not contain any studies with human participants or animals performed by any of the authors.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethics approval and consent to participate"}}],"article-number":"36"}}