{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,11]],"date-time":"2025-09-11T21:05:43Z","timestamp":1757624743301,"version":"3.44.0"},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"13","license":[{"start":{"date-parts":[[2025,8,16]],"date-time":"2025-08-16T00:00:00Z","timestamp":1755302400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,8,16]],"date-time":"2025-08-16T00:00:00Z","timestamp":1755302400000},"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":"crossref","award":["62402164"],"award-info":[{"award-number":["62402164"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Supercomput"],"DOI":"10.1007\/s11227-025-07724-7","type":"journal-article","created":{"date-parts":[[2025,8,16]],"date-time":"2025-08-16T05:59:38Z","timestamp":1755323978000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["A dual-evaluation-mode local-search for the minimum dominating set problem on ultra-large sparse graphs"],"prefix":"10.1007","volume":"81","author":[{"given":"Yexin","family":"Peng","sequence":"first","affiliation":[]},{"given":"Mao","family":"Luo","sequence":"additional","affiliation":[]},{"given":"Xinyun","family":"Wu","sequence":"additional","affiliation":[]},{"given":"Caiquan","family":"Xiong","sequence":"additional","affiliation":[]},{"given":"Hui","family":"Kong","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,8,16]]},"reference":[{"issue":"12","key":"7724_CR1","doi-asserted-by":"publisher","first-page":"7823","DOI":"10.1109\/TSMC.2020.2987163","volume":"51","author":"D Zhao","year":"2020","unstructured":"Zhao D, Xiao G, Wang Z, Wang L, Xu L (2020) Minimum dominating set of multiplex networks: definition, application, and identification. IEEE Transactions on Systems Man and Cybernetics Systems 51(12):7823\u20137837","journal-title":"IEEE Transactions on Systems Man and Cybernetics Systems"},{"key":"7724_CR2","doi-asserted-by":"publisher","DOI":"10.1016\/j.cnsns.2023.107753","volume":"130","author":"Y Liu","year":"2024","unstructured":"Liu Y, Liang G, Wang X, Wang Z, Zhu P, Wang Z (2024) Efficient approaches for attaining epidemic-free networks with minimum edge removal set. Commun Nonlinear Sci Numer Simul 130:107753","journal-title":"Commun Nonlinear Sci Numer Simul"},{"issue":"1","key":"7724_CR3","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1038\/s41467-023-44257-0","volume":"15","author":"M Engsig","year":"2024","unstructured":"Engsig M, Tejedor A, Moreno Y, Foufoula-Georgiou E, Kasmi C (2024) Domirank centrality reveals structural fragility of complex networks via node dominance. Nat Commun 15(1):12","journal-title":"Nat Commun"},{"issue":"12","key":"7724_CR4","doi-asserted-by":"publisher","first-page":"2258","DOI":"10.1109\/JAS.2023.123315","volume":"10","author":"X Chen","year":"2023","unstructured":"Chen X, Tang C, Zhang Z (2023) A game theoretic approach for a minimal secure dominating set. IEEE\/CAA Journal of Automatica Sinica 10(12):2258\u20132268","journal-title":"IEEE\/CAA Journal of Automatica Sinica"},{"issue":"05","key":"7724_CR5","doi-asserted-by":"publisher","first-page":"1750021","DOI":"10.1142\/S0219720017500214","volume":"15","author":"Y Chu","year":"2017","unstructured":"Chu Y, Wang Z, Wang R, Zhang N, Li J, Hu Y, Teng M, Wang Y (2017) Wdnfinder: A method for minimum driver node set detection and analysis in directed and weighted biological network. J Bioinform Comput Biol 15(05):1750021","journal-title":"J Bioinform Comput Biol"},{"key":"7724_CR6","doi-asserted-by":"crossref","unstructured":"Alofairi AA, Mabrouk E, Elsemman IE (2021) Constraint-based models for dominating protein interaction networks. IET Systems Biology (1)","DOI":"10.1049\/syb2.12021"},{"issue":"3","key":"7724_CR7","first-page":"389","volume":"9","author":"RC Brewster","year":"2024","unstructured":"Brewster RC, Mynhardt CM, Teshima LE (2024) Reconfiguring minimum independent dominating sets in graphs. Communications in Combinatorics and Optimization 9(3):389\u2013411","journal-title":"Communications in Combinatorics and Optimization"},{"key":"7724_CR8","doi-asserted-by":"crossref","unstructured":"Fomin FV, Kratsch D, Woeginger GJ (2005) Exact (exponential) algorithms for the dominating set problem. In: Graph-Theoretic Concepts in Computer Science: 30th International Workshop, WG 2004, Bad Honnef, Germany, June 21-23, 2004. Revised Papers 30, pp. 245\u2013256. Springer","DOI":"10.1007\/978-3-540-30559-0_21"},{"issue":"2","key":"7724_CR9","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1016\/j.jda.2005.03.002","volume":"4","author":"F Grandoni","year":"2006","unstructured":"Grandoni F (2006) A note on the complexity of minimum dominating set. Journal of Discrete Algorithms 4(2):209\u2013214","journal-title":"Journal of Discrete Algorithms"},{"issue":"17","key":"7724_CR10","doi-asserted-by":"publisher","first-page":"3291","DOI":"10.1016\/j.dam.2008.05.035","volume":"156","author":"I Schiermeyer","year":"2008","unstructured":"Schiermeyer I (2008) Efficiency in exponential time for domination-type problems. Discret Appl Math 156(17):3291\u20133297","journal-title":"Discret Appl Math"},{"key":"7724_CR11","doi-asserted-by":"crossref","unstructured":"Iwata Y (2012) A faster algorithm for dominating set analyzed by the potential method. In: Parameterized and Exact Computation: 6th International Symposium, IPEC 2011, Saarbr\u00fccken, Germany, September 6-8, 2011. Revised Selected Papers 6, pp. 41\u201354. Springer","DOI":"10.1007\/978-3-642-28050-4_4"},{"key":"7724_CR12","doi-asserted-by":"crossref","unstructured":"Cai S, Hou W, Wang Y, Luo C, Lin Q (2021) Two-goal local search and inference rules for minimum dominating set. In: Proceedings of the Twenty-ninth International Conference on International Joint Conferences on Artificial Intelligence, pp. 1467\u20131473","DOI":"10.24963\/ijcai.2020\/204"},{"key":"7724_CR13","doi-asserted-by":"crossref","unstructured":"Lamm S, Sanders P, Schulz C, Strash D, Werneck RF (2016) Finding near-optimal independent sets at scale. In: 2016 Proceedings of the Eighteenth Workshop on Algorithm Engineering and Experiments (ALENEX), pp. 138\u2013150. SIAM","DOI":"10.1137\/1.9781611974317.12"},{"key":"7724_CR14","doi-asserted-by":"crossref","unstructured":"Dahlum J, Lamm S, Sanders P, Schulz C, Strash D, Werneck RF (2016) Accelerating local search for the maximum independent set problem. In: Experimental Algorithms: 15th International Symposium, SEA, St. Petersburg, Russia, June 5-8, 2016, Proceedings 15, pp. 118\u2013133. Springer","DOI":"10.1007\/978-3-319-38851-9_9"},{"key":"7724_CR15","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1016\/j.tcs.2015.09.023","volume":"609","author":"T Akiba","year":"2016","unstructured":"Akiba T, Iwata Y (2016) Branch-and-reduce exponential\/fpt algorithms in practice: A case study of vertex cover. Theoret Comput Sci 609:211\u2013225","journal-title":"Theoret Comput Sci"},{"key":"7724_CR16","doi-asserted-by":"publisher","DOI":"10.1016\/j.eswa.2021.115185","volume":"182","author":"C Quan","year":"2021","unstructured":"Quan C, Guo P (2021) A local search method based on edge age strategy for minimum vertex cover problem in massive graphs. Expert Syst Appl 182:115185","journal-title":"Expert Syst Appl"},{"key":"7724_CR17","doi-asserted-by":"publisher","DOI":"10.1016\/j.ins.2023.119140","volume":"642","author":"C Liu","year":"2023","unstructured":"Liu C, Ge S, Zhang Y (2023) Identifying the cardinality-constrained critical nodes with a hybrid evolutionary algorithm. Inf Sci 642:119140","journal-title":"Inf Sci"},{"issue":"6","key":"7724_CR18","doi-asserted-by":"publisher","first-page":"4960","DOI":"10.1109\/TCYB.2020.3025819","volume":"52","author":"E Zhu","year":"2020","unstructured":"Zhu E, Jiang F, Liu C, Xu J (2020) Partition independent set and reduction-based approach for partition coloring problem. IEEE Transactions on Cybernetics 52(6):4960\u20134969","journal-title":"IEEE Transactions on Cybernetics"},{"key":"7724_CR19","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":"1","key":"7724_CR20","first-page":"5650364","volume":"2017","author":"S Alharbi","year":"2017","unstructured":"Alharbi S, Venkat I (2017) A genetic algorithm based approach for solving the minimum dominating set of queens problem. Journal of Optimization 2017(1):5650364","journal-title":"Journal of Optimization"},{"key":"7724_CR21","doi-asserted-by":"crossref","unstructured":"Potluri A, Singh A (2011) Two hybrid meta-heuristic approaches for minimum dominating set problem. In: Swarm, Evolutionary, and Memetic Computing: Second International Conference, SEMCCO 2011, Visakhapatnam, Andhra Pradesh, India, December 19-21, 2011, Proceedings, Part II 2, pp. 97\u2013104. Springer","DOI":"10.1007\/978-3-642-27242-4_12"},{"key":"7724_CR22","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1007\/s13042-011-0043-y","volume":"3","author":"A-R Hedar","year":"2012","unstructured":"Hedar A-R, Ismail R (2012) Simulated annealing with stochastic local search for minimum dominating set problem. Int J Mach Learn Cybern 3:97\u2013109","journal-title":"Int J Mach Learn Cybern"},{"key":"7724_CR23","doi-asserted-by":"publisher","DOI":"10.1016\/j.knosys.2024.111950","volume":"298","author":"E Zhu","year":"2024","unstructured":"Zhu E, Zhang Y, Wang S, Strash D, Liu C (2024) A dual-mode local search algorithm for solving the minimum dominating set problem. Knowl-Based Syst 298:111950","journal-title":"Knowl-Based Syst"},{"issue":"9\u201310","key":"7724_CR24","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\u201310):1672\u20131696","journal-title":"Artif Intell"},{"key":"7724_CR25","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1613\/jair.5205","volume":"58","author":"Y Wang","year":"2017","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. Journal of Artificial Intelligence Research 58:267\u2013295","journal-title":"Journal of Artificial Intelligence Research"},{"key":"7724_CR26","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: IJCAI, pp. 1514\u20131522","DOI":"10.24963\/ijcai.2018\/210"},{"key":"7724_CR27","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1016\/j.ins.2017.10.033","volume":"426","author":"D Chalupa","year":"2018","unstructured":"Chalupa D (2018) An order-based algorithm for minimum dominating set with application in graph mining. Inf Sci 426:101\u2013116","journal-title":"Inf Sci"},{"issue":"1","key":"7724_CR28","doi-asserted-by":"publisher","first-page":"76","DOI":"10.1016\/j.asoc.2012.07.009","volume":"13","author":"A Potluri","year":"2013","unstructured":"Potluri A, Singh A (2013) Hybrid metaheuristic algorithms for minimum weight dominating set. Appl Soft Comput 13(1):76\u201388","journal-title":"Appl Soft Comput"},{"key":"7724_CR29","doi-asserted-by":"crossref","unstructured":"Fan Y, Lai Y, Li C, Li N, Ma Z, Zhou J, Latecki LJ, Su K (2019) Efficient local search for minimum dominating sets in large graphs. In: International Conference on Database Systems for Advanced Applications, pp. 211\u2013228. Springer","DOI":"10.1007\/978-3-030-18579-4_13"},{"key":"7724_CR30","doi-asserted-by":"crossref","unstructured":"Cai, S., Hou, W., Wang, Y., Luo, C., Lin, Q.: Two-goal local search and inference rules for minimum dominating set. In: Proceedings of the Twenty-ninth International Conference on International Joint Conferences on Artificial Intelligence, pp. 1467\u20131473 (2021)","DOI":"10.24963\/ijcai.2020\/204"},{"issue":"4","key":"7724_CR31","doi-asserted-by":"publisher","first-page":"789","DOI":"10.1016\/S0022-0000(03)00074-6","volume":"67","author":"L Cai","year":"2003","unstructured":"Cai L, Juedes DW (2003) On the existence of subexponential parameterized algorithms. J Comput Syst Sci 67(4):789\u2013807","journal-title":"J Comput Syst Sci"},{"key":"7724_CR32","doi-asserted-by":"crossref","unstructured":"Rossi, R., Ahmed, N.: The network data repository with interactive graph analytics and visualization. In: Proceedings of the AAAI Conference on Artificial Intelligence, vol. 29 (2015)","DOI":"10.1609\/aaai.v29i1.9277"}],"container-title":["The Journal of Supercomputing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11227-025-07724-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11227-025-07724-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11227-025-07724-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,9]],"date-time":"2025-09-09T14:49:58Z","timestamp":1757429398000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11227-025-07724-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,8,16]]},"references-count":32,"journal-issue":{"issue":"13","published-online":{"date-parts":[[2025,8]]}},"alternative-id":["7724"],"URL":"https:\/\/doi.org\/10.1007\/s11227-025-07724-7","relation":{},"ISSN":["1573-0484"],"issn-type":[{"type":"electronic","value":"1573-0484"}],"subject":[],"published":{"date-parts":[[2025,8,16]]},"assertion":[{"value":"30 July 2025","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 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 no Conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}],"article-number":"1244"}}