{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T07:38:58Z","timestamp":1740123538311,"version":"3.37.3"},"reference-count":34,"publisher":"Springer Science and Business Media LLC","issue":"9","license":[{"start":{"date-parts":[[2022,2,21]],"date-time":"2022-02-21T00:00:00Z","timestamp":1645401600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,2,21]],"date-time":"2022-02-21T00:00:00Z","timestamp":1645401600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100010248","name":"Zhejiang Province Public Welfare Technology Application Research Project","doi-asserted-by":"publisher","award":["LGG19F030010"],"award-info":[{"award-number":["LGG19F030010"]}],"id":[{"id":"10.13039\/501100010248","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["61703183","62162063"],"award-info":[{"award-number":["61703183","62162063"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["61773410","61906069"],"award-info":[{"award-number":["61773410","61906069"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Science and Technology Program of Guangzhou","award":["202002030260"],"award-info":[{"award-number":["202002030260"]}]},{"DOI":"10.13039\/501100010273","name":"Roberto and Cornelia Pallotti\u2019s Legacy for Cancer Research","doi-asserted-by":"publisher","award":["yy2020bsky050"],"award-info":[{"award-number":["yy2020bsky050"]}],"id":[{"id":"10.13039\/501100010273","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Supercomput"],"published-print":{"date-parts":[[2022,6]]},"DOI":"10.1007\/s11227-022-04342-5","type":"journal-article","created":{"date-parts":[[2022,2,21]],"date-time":"2022-02-21T17:07:12Z","timestamp":1645463232000},"page":"11949-11973","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Performance analysis of evolutionary algorithm for the maximum internal spanning tree problem"],"prefix":"10.1007","volume":"78","author":[{"given":"Xiaoyun","family":"Xia","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7121-4143","authenticated-orcid":false,"given":"Zhengxin","family":"Huang","sequence":"additional","affiliation":[]},{"given":"Xue","family":"Peng","sequence":"additional","affiliation":[]},{"given":"Zefeng","family":"Chen","sequence":"additional","affiliation":[]},{"given":"Yi","family":"Xiang","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,2,21]]},"reference":[{"issue":"1","key":"4342_CR1","doi-asserted-by":"publisher","first-page":"661","DOI":"10.1007\/s00500-019-04495-1","volume":"24","author":"S Al-Janabi","year":"2020","unstructured":"Al-Janabi S, Mohammad M, Al-Sultan A (2020) A new method for prediction of air pollution based on intelligent computation. Soft Comput 24(1):661\u2013680. https:\/\/doi.org\/10.1007\/s00500-019-04495-1","journal-title":"Soft Comput"},{"issue":"21","key":"4342_CR2","doi-asserted-by":"publisher","first-page":"14199","DOI":"10.1007\/s00521-021-06067-7","volume":"33","author":"S Al-Janabi","year":"2021","unstructured":"Al-Janabi S, Alkaim A, Al-Janabi E, Aljeboree A, Mustafa M (2021) Intelligent forecaster of concentrations (PM2. 5, PM10, NO2, CO, O3, SO2) caused air pollution (IFCsAP). Neural Comput Appli 33(21):14199\u2013229. https:\/\/doi.org\/10.1007\/s00521-021-06067-7","journal-title":"Neural Comput Appli"},{"issue":"1","key":"4342_CR3","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1007\/s00453-011-9575-5","volume":"65","author":"D Binkele-Raible","year":"2013","unstructured":"Binkele-Raible D, Fernau H, Gaspers S, Liedloff M (2013) Exact and parameterized algorithms for max internal spanning tree. Algorithmica 65(1):95\u2013128. https:\/\/doi.org\/10.1007\/s00453-011-9575-5","journal-title":"Algorithmica"},{"issue":"2","key":"4342_CR4","doi-asserted-by":"publisher","first-page":"687","DOI":"10.1137\/15M1048975","volume":"31","author":"A Bj\u00f3rklund","year":"2017","unstructured":"Bj\u00f3rklund A, Kamat V, Kowalik \u0141, Zehavi M (2017) Spotting trees with few leaves. SIAM J Discret Math 31(2):687\u2013713. https:\/\/doi.org\/10.1137\/15M1048975","journal-title":"SIAM J Discret Math"},{"key":"4342_CR5","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1016\/j.dam.2018.08.011","volume":"272","author":"K Casel","year":"2020","unstructured":"Casel K, Dreier J, Fernau H, Gobbert M, Kuinke P, Villaamil FS, Schmid ML, van Leeuwen EJ (2020) Complexity of independency and cliquy trees. Discret Appl Math 272:2\u201315. https:\/\/doi.org\/10.1016\/j.dam.2018.08.011","journal-title":"Discret Appl Math"},{"issue":"11\u201312","key":"4342_CR6","doi-asserted-by":"publisher","first-page":"4167","DOI":"10.1007\/s00453-018-00533-w","volume":"81","author":"ZZ Chen","year":"2019","unstructured":"Chen ZZ, Lin G, Wang L, Chen Y, Wang D (2019) Approximation algorithms for the maximum weight internal spanning tree problem. Algorithmica 81(11\u201312):4167\u20134199. https:\/\/doi.org\/10.1007\/s00453-018-00533-w","journal-title":"Algorithmica"},{"issue":"4","key":"4342_CR7","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3472304","volume":"1","author":"B Doerr","year":"2021","unstructured":"Doerr B, Neumann F (2021) A survey on recent progress in the theory of evolutionary algorithms for discrete optimization. ACM Trans Evolut Learn Optim 1(4):1\u201343. https:\/\/doi.org\/10.1145\/3472304","journal-title":"ACM Trans Evolut Learn Optim"},{"doi-asserted-by":"publisher","unstructured":"Doerr B, Neumann F, Sutton AM (2015) Improved runtime bounds for the (1+1) EA on random 3-CNF formulas based on fitness-distance correlation. In: Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation, pp 1415\u20131422, https:\/\/doi.org\/10.1145\/2739480.2754659","key":"4342_CR8","DOI":"10.1145\/2739480.2754659"},{"doi-asserted-by":"publisher","unstructured":"Eiben AE, Smith JE (2015) Introduction to evolutionary computing. Springer. https:\/\/doi.org\/10.1007\/978-3-662-44874-8","key":"4342_CR9","DOI":"10.1007\/978-3-662-44874-8"},{"key":"4342_CR10","doi-asserted-by":"publisher","first-page":"122992","DOI":"10.1016\/j.physa.2019.122992","volume":"539","author":"Z Huang","year":"2020","unstructured":"Huang Z, Zhou Y, Xia X, Lai X (2020) An improved (1+ 1) evolutionary algorithm for k-median clustering problem with performance guarantee. Physica A 539:122992. https:\/\/doi.org\/10.1016\/j.physa.2019.122992","journal-title":"Physica A"},{"issue":"4","key":"4342_CR11","doi-asserted-by":"publisher","first-page":"797","DOI":"10.1007\/s00453-013-9827-7","volume":"71","author":"M Knauer","year":"2015","unstructured":"Knauer M, Spoerhase J (2015) Better approximation algorithms for the maximum internal spanning tree problem. Algorithmica 71(4):797\u2013811. https:\/\/doi.org\/10.1007\/s00453-013-9827-7","journal-title":"Algorithmica"},{"issue":"4","key":"4342_CR12","doi-asserted-by":"publisher","first-page":"707","DOI":"10.1162\/evco\\_a_00200","volume":"25","author":"X Lai","year":"2017","unstructured":"Lai X, Zhou Y, Xia X, Zhang Q (2017) Performance analysis of evolutionary algorithms for steiner tree problems. Evol Comput 25(4):707\u2013723. https:\/\/doi.org\/10.1162\/evco_a_00200","journal-title":"Evol Comput"},{"key":"4342_CR13","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1016\/j.ic.2016.11.003","volume":"252","author":"W Li","year":"2017","unstructured":"Li W, Cao Y, Chen J, Wang J (2017) Deeper local search for parameterized and approximation algorithms for maximum internal spanning tree. Inf Comput 252:187\u2013200. https:\/\/doi.org\/10.1016\/j.ic.2016.11.003","journal-title":"Inf Comput"},{"doi-asserted-by":"publisher","unstructured":"Li X, Zhu D (2014) Approximating the maximum internal spanning tree problem via a maximum path-cycle cover. In: International symposium on algorithms and computation, pp 467\u2013478, https:\/\/doi.org\/10.1007\/978-3-319-13075-0_37","key":"4342_CR14","DOI":"10.1007\/978-3-319-13075-0_37"},{"key":"4342_CR15","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1016\/j.jcss.2021.01.001","volume":"118","author":"X Li","year":"2021","unstructured":"Li X, Zhu D, Wang L (2021) A 4\/3-approximation algorithm for the maximum internal spanning tree problem. J Comput Syst Sci 118:131\u2013140. https:\/\/doi.org\/10.1016\/j.jcss.2021.01.001","journal-title":"J Comput Syst Sci"},{"unstructured":"Muhlenbein H (1992) How genetic algorithms really work: I. mutation and hillclimbing. In: Proceeding of 2nd International Conference on Parallel Problem Solving from Nature, 1992, Elsevier, pp 15\u201325","key":"4342_CR16"},{"issue":"1","key":"4342_CR17","doi-asserted-by":"publisher","first-page":"32","DOI":"10.1016\/j.tcs.2006.11.002","volume":"378","author":"F Neumann","year":"2007","unstructured":"Neumann F, Wegener I (2007) Randomized local search, evolutionary algorithms, and the minimum spanning tree problem. Theoret Comput Sci 378(1):32\u201340. https:\/\/doi.org\/10.1016\/j.tcs.2006.11.002","journal-title":"Theoret Comput Sci"},{"doi-asserted-by":"publisher","unstructured":"Neumann F, Witt C (2010) Bioinspired computation in combinatorial optimization. Natural Computing Series, Springer. https:\/\/doi.org\/10.1007\/978-3-642-16544-3","key":"4342_CR18","DOI":"10.1007\/978-3-642-16544-3"},{"issue":"7","key":"4342_CR19","doi-asserted-by":"publisher","first-page":"111884","DOI":"10.1016\/j.disc.2020.111884","volume":"343","author":"K Ozeki","year":"2020","unstructured":"Ozeki K, Wiener G, Zamfirescu CT (2020) On minimum leaf spanning trees and a criticality notion. Discret Math 343(7):111884. https:\/\/doi.org\/10.1016\/j.disc.2020.111884","journal-title":"Discret Math"},{"key":"4342_CR20","doi-asserted-by":"publisher","first-page":"20","DOI":"10.1016\/j.tcs.2019.03.003","volume":"832","author":"M Pourhassan","year":"2020","unstructured":"Pourhassan M, Roostapour V, Neumann F (2020) Runtime analysis of rls and (1+ 1) EA for the dynamic weighted vertex cover problem. Theoret Comput Sci 832:20\u201341. https:\/\/doi.org\/10.1016\/j.tcs.2019.03.003","journal-title":"Theoret Comput Sci"},{"doi-asserted-by":"publisher","unstructured":"Prieto E, Sloper C (2003) Either\/or: Using vertex cover structure in designing FPT-algorithms - the case of k-internal spanning tree. In: Algorithms and data structures, international workshop, Wads, Ottawa, Ontario, Canada, July 30-august, https:\/\/doi.org\/10.1007\/978-3-540-45078-8_41","key":"4342_CR21","DOI":"10.1007\/978-3-540-45078-8_41"},{"issue":"50","key":"4342_CR22","doi-asserted-by":"publisher","first-page":"5273","DOI":"10.1016\/j.tcs.2009.08.029","volume":"410","author":"G Salamon","year":"2009","unstructured":"Salamon G (2009) Approximating the maximum internal spanning tree problem. Theoret Comput Sci 410(50):5273\u20135284. https:\/\/doi.org\/10.1016\/j.tcs.2009.08.029","journal-title":"Theoret Comput Sci"},{"key":"4342_CR23","doi-asserted-by":"publisher","first-page":"1209","DOI":"10.1016\/j.endm.2010.05.153","volume":"36","author":"G Salamon","year":"2010","unstructured":"Salamon G (2010) A survey on algorithms for the maximum internal spanning tree and related problems. Electron Notes Discret Math 36:1209\u20131216. https:\/\/doi.org\/10.1016\/j.endm.2010.05.153","journal-title":"Electron Notes Discret Math"},{"issue":"5","key":"4342_CR24","doi-asserted-by":"publisher","first-page":"164","DOI":"10.1016\/j.ipl.2007.08.030","volume":"105","author":"G Salamon","year":"2008","unstructured":"Salamon G, Wiener G (2008) On finding spanning trees with few leaves. Inf Process Lett 105(5):164\u2013169. https:\/\/doi.org\/10.1016\/j.ipl.2007.08.030","journal-title":"Inf Process Lett"},{"key":"4342_CR25","doi-asserted-by":"publisher","first-page":"24","DOI":"10.1016\/j.engappai.2017.09.014","volume":"67","author":"M Sangdani","year":"2018","unstructured":"Sangdani M, Tavakolpour-Saleh A, Lotfavar A (2018) Genetic algorithm-based optimal computed torque control of a vision-based tracker robot: simulation and experiment. Eng Appl Artif Intell 67:24\u201338. https:\/\/doi.org\/10.1016\/j.engappai.2017.09.014","journal-title":"Eng Appl Artif Intell"},{"issue":"4","key":"4342_CR26","doi-asserted-by":"publisher","first-page":"906","DOI":"10.1007\/s00453-019-00662-w","volume":"83","author":"F Shi","year":"2021","unstructured":"Shi F, Neumann F, Wang J (2021) Runtime performances of randomized search heuristics for the dynamic weighted vertex cover problem. Algorithmica 83(4):906\u2013939. https:\/\/doi.org\/10.1007\/s00453-019-00662-w","journal-title":"Algorithmica"},{"key":"4342_CR27","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1016\/j.tcs.2021.09.003","volume":"893","author":"F Shi","year":"2021","unstructured":"Shi F, Neumann F, Wang J (2021) Time complexity analysis of evolutionary algorithms for 2-hop (1, 2)-minimum spanning tree problem. Theor Comput Sci 893:159\u201375. https:\/\/doi.org\/10.1016\/j.tcs.2021.09.003","journal-title":"Theor Comput Sci"},{"issue":"2","key":"4342_CR28","doi-asserted-by":"publisher","first-page":"755","DOI":"10.3233\/JIFS-169369","volume":"34","author":"M Sundhararajan","year":"2018","unstructured":"Sundhararajan M, Gao XZ, Nejad HV (2018) Artificial intelligent techniques and its applications. J Intell Fuzzy Syst 34(2):755\u2013760. https:\/\/doi.org\/10.3233\/JIFS-169369","journal-title":"J Intell Fuzzy Syst"},{"doi-asserted-by":"publisher","unstructured":"Williamson DP, Shmoys DB (2011) The design of approximation algorithms. Cambridge University Press. https:\/\/doi.org\/10.1017\/CBO9780511921735","key":"4342_CR29","DOI":"10.1017\/CBO9780511921735"},{"issue":"4","key":"4342_CR30","doi-asserted-by":"publisher","first-page":"154329","DOI":"10.1007\/s11704-020-9464-7","volume":"15","author":"X Xia","year":"2021","unstructured":"Xia X, Peng X, Liao W (2021) On the analysis of ant colony optimization for the maximum independent set problem. Front Comp Sci 15(4):154329. https:\/\/doi.org\/10.1007\/s11704-020-9464-7","journal-title":"Front Comp Sci"},{"doi-asserted-by":"publisher","unstructured":"Xie Y, Neumann A, Neumann F, Sutton AM (2021) Runtime analysis of RLS and the (1+1) EA for the chance-constrained knapsack problem with correlated uniform weights. In: Chicano F, Krawiec K (eds) Proceedings of the 2021 Annual Conference on Genetic and Evolutionary Computation Conference, ACM, pp 1187\u20131194, https:\/\/doi.org\/10.1145\/3449639.3459381","key":"4342_CR31","DOI":"10.1145\/3449639.3459381"},{"issue":"1","key":"4342_CR32","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1007\/s00453-016-0166-3","volume":"78","author":"M Zehavi","year":"2017","unstructured":"Zehavi M (2017) Algorithms for k-internal out-branching and k-tree in bounded degree graphs. Algorithmica 78(1):319\u2013341. https:\/\/doi.org\/10.1007\/s00453-016-0166-3","journal-title":"Algorithmica"},{"issue":"1","key":"4342_CR33","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1007\/s00453-014-9898-0","volume":"73","author":"Y Zhou","year":"2015","unstructured":"Zhou Y, Zhang J, Wang Y (2015) Performance analysis of the (1+ 1) evolutionary algorithm for the multiprocessor scheduling problem. Algorithmica 73(1):21\u201341. https:\/\/doi.org\/10.1007\/s00453-014-9898-0","journal-title":"Algorithmica"},{"doi-asserted-by":"publisher","unstructured":"Zhou ZH, Yu Y, Qian C (2019) Evolutionary learning: advances in theories and algorithms. Springer. https:\/\/doi.org\/10.1007\/978-981-13-5956-9","key":"4342_CR34","DOI":"10.1007\/978-981-13-5956-9"}],"container-title":["The Journal of Supercomputing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11227-022-04342-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11227-022-04342-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11227-022-04342-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,5,19]],"date-time":"2022-05-19T10:27:03Z","timestamp":1652956023000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11227-022-04342-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,2,21]]},"references-count":34,"journal-issue":{"issue":"9","published-print":{"date-parts":[[2022,6]]}},"alternative-id":["4342"],"URL":"https:\/\/doi.org\/10.1007\/s11227-022-04342-5","relation":{},"ISSN":["0920-8542","1573-0484"],"issn-type":[{"type":"print","value":"0920-8542"},{"type":"electronic","value":"1573-0484"}],"subject":[],"published":{"date-parts":[[2022,2,21]]},"assertion":[{"value":"4 January 2022","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 February 2022","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}