{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,19]],"date-time":"2026-05-19T20:51:20Z","timestamp":1779223880197,"version":"3.51.4"},"reference-count":46,"publisher":"MIT Press","issue":"2","content-domain":{"domain":["direct.mit.edu"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2024,6,3]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>We contribute to the efficient approximation of the Pareto-set for the classical NP-hard multiobjective minimum spanning tree problem (moMST) adopting evolutionary computation. More precisely, by building upon preliminary work, we analyze the neighborhood structure of Pareto-optimal spanning trees and design several highly biased sub-graph-based mutation operators founded on the gained insights. In a nutshell, these operators replace (un)connected sub-trees of candidate solutions with locally optimal sub-trees. The latter (biased) step is realized by applying Kruskal's single-objective MST algorithm to a weighted sum scalarization of a sub-graph.<\/jats:p>\n               <jats:p>We prove runtime complexity results for the introduced operators and investigate the desirable Pareto-beneficial property. This property states that mutants cannot be dominated by their parent. Moreover, we perform an extensive experimental benchmark study to showcase the operator's practical suitability. Our results confirm that the sub-graph-based operators beat baseline algorithms from the literature even with severely restricted computational budget in terms of function evaluations on four different classes of complete graphs with different shapes of the Pareto-front.<\/jats:p>","DOI":"10.1162\/evco_a_00335","type":"journal-article","created":{"date-parts":[[2023,6,8]],"date-time":"2023-06-08T19:52:31Z","timestamp":1686253951000},"page":"143-175","update-policy":"https:\/\/doi.org\/10.1162\/mitpressjournals.corrections.policy","source":"Crossref","is-referenced-by-count":3,"title":["On Single-Objective Sub-Graph-Based Mutation for Solving the Bi-Objective Minimum Spanning Tree Problem"],"prefix":"10.1162","volume":"32","author":[{"given":"Jakob","family":"Bossek","sequence":"first","affiliation":[{"name":"AI Methodology, Department of Computer Science, RWTH Aachen University, Germany bossek@aim.rwth-aachen.de"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christian","family":"Grimme","sequence":"additional","affiliation":[{"name":"Statistics and Optimization, Department of Information Systems, University of M\u00fcnster, Germany christian.grimme@wi.uni-muenster.de"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"281","published-online":{"date-parts":[[2024,6,3]]},"reference":[{"key":"2024060313545278300_B1","doi-asserted-by":"crossref","DOI":"10.1201\/9781584888215","volume-title":"Algorithms and theory of computation handbook","author":"Atallah","year":"2009","edition":"2nd ed"},{"issue":"3","key":"2024060313545278300_B2","first-page":"467","article-title":"Data structures for direct spanning tree representations in mutation-based evolutionary algorithms","volume":"24","author":"Barbosa","year":"2020","journal-title":"IEEE Transactions on Evolutionary Computation"},{"issue":"3","key":"2024060313545278300_B3","doi-asserted-by":"publisher","first-page":"1653","DOI":"10.1016\/j.ejor.2006.08.008","article-title":"SMS-EMOA: Multiobjective selection based on dominated hypervolume","volume":"181","author":"Beume","year":"2007","journal-title":"European Journal of Operational Research"},{"key":"2024060313545278300_B4","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-04378-3","volume-title":"The theory of evolution strategies","author":"Beyer","year":"2001"},{"key":"2024060313545278300_B5","doi-asserted-by":"crossref","first-page":"1187","DOI":"10.1145\/3067695.3082470","article-title":"ecr 2.0: A modular framework for evolutionary computation in R","volume-title":"Genetic and Evolutionary Computation Conference (Companion)","author":"Bossek","year":"2017"},{"issue":"17","key":"2024060313545278300_B6","doi-asserted-by":"publisher","DOI":"10.21105\/joss.00374","article-title":"mcMST: A toolbox for the multi-criteria minimum spanning tree problem","volume":"2","author":"Bossek","year":"2017","journal-title":"The Journal of Open Source Software"},{"issue":"22","key":"2024060313545278300_B7","doi-asserted-by":"publisher","DOI":"10.21105\/joss.00528","article-title":"grapherator: A modular multi-step graph generator","volume":"3","author":"Bossek","year":"2018","journal-title":"The Journal of Open Source Software"},{"key":"2024060313545278300_B8","first-page":"3280","article-title":"A Pareto-beneficial sub-tree mutation for the multicriteria minimum spanning tree problem","author":"Bossek","year":"2017","journal-title":"IEEE Symposium Series on Computational Intelligence"},{"key":"2024060313545278300_B9","doi-asserted-by":"crossref","first-page":"516","DOI":"10.1145\/3321707.3321818","article-title":"On the benefits of biased edge-exchange mutation for the multi-criteria spanning tree problem","volume-title":"Genetic and Evolutionary Computation Conference","author":"Bossek","year":"2019"},{"key":"2024060313545278300_B10","doi-asserted-by":"crossref","first-page":"442","DOI":"10.1109\/SFCS.1989.63516","article-title":"Generating random spanning trees","volume-title":"30th Annual Symposium on Foundations of Computer Science","author":"Broder","year":"1989"},{"issue":"1","key":"2024060313545278300_B11","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1016\/0166-218X(83)90014-8","article-title":"On the complexity of finding multi-constrained spanning trees","volume":"5","author":"Camerini","year":"1983","journal-title":"Discrete Applied Mathematics"},{"key":"2024060313545278300_B12","first-page":"376","article-title":"A theorem on trees","volume":"23","author":"Cayley","year":"1889","journal-title":"The Quarterly Journal of Mathematics"},{"key":"2024060313545278300_B13","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-23424-8","volume-title":"Variants of evolutionary algorithms for real-world applications","author":"Chiong","year":"2012"},{"key":"2024060313545278300_B14","author":"Christofides","year":"1976","journal-title":"Worst-case analysis of a new heuristic for the travelling salesman problem"},{"key":"2024060313545278300_B15","volume-title":"Evolutionary algorithms for solving multi-objective problems","author":"Coello","year":"2007","edition":"2nd ed"},{"issue":"3","key":"2024060313545278300_B16","doi-asserted-by":"publisher","first-page":"481","DOI":"10.1007\/BF00938448","article-title":"Efficient spanning trees","volume":"45","author":"Corley","year":"1985","journal-title":"Journal of Optimization Theory and Applications"},{"key":"2024060313545278300_B17","volume-title":"Introduction to algorithms","author":"Cormen","year":"2009","edition":"3rd ed"},{"key":"2024060313545278300_B18","volume-title":"Optimization for engineering design\u2014algorithms and examples","author":"Deb","year":"2012","edition":"2nd ed"},{"issue":"2","key":"2024060313545278300_B19","doi-asserted-by":"publisher","first-page":"182","DOI":"10.1109\/4235.996017","article-title":"A fast and elitist multiobjective genetic algorithm: NSGA-II","volume":"6","author":"Deb","year":"2002","journal-title":"IEEE Transactions on Evolutionary Computation"},{"key":"2024060313545278300_B20","volume-title":"Multicriteria optimization","author":"Ehrgott","year":"2005"},{"key":"2024060313545278300_B21","doi-asserted-by":"publisher","first-page":"449","DOI":"10.1016\/j.entcs.2019.08.040","article-title":"A multi-agent transgenetic algorithm for the bi-objective spanning tree problem","volume":"346","author":"Fernandes","year":"2019","journal-title":"Electronic Notes in Theoretical Computer Science"},{"issue":"3","key":"2024060313545278300_B22","doi-asserted-by":"publisher","first-page":"411","DOI":"10.1016\/0196-6774(88)90031-4","article-title":"Algorithms for two bottleneck optimization problems","volume":"9","author":"Gabow","year":"1988","journal-title":"Journal on Algorithms"},{"key":"2024060313545278300_B23","first-page":"343","article-title":"Pr\u00fcfer numbers: A poor representation of spanning trees for evolutionary search","volume-title":"Genetic and Evolutionary Computation Conference","author":"Gottlieb","year":"2001"},{"key":"2024060313545278300_B24","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1007\/BF02032304","article-title":"On spanning tree problems with multiple objectives","volume":"52","author":"Hamacher","year":"1994","journal-title":"Annals of Operations Research"},{"issue":"3","key":"2024060313545278300_B25","doi-asserted-by":"publisher","first-page":"188","DOI":"10.1137\/0203015","article-title":"Optimum communication spanning trees","volume":"3","author":"Hu","year":"1974","journal-title":"SIAM Journal on Computing"},{"issue":"8","key":"2024060313545278300_B26","doi-asserted-by":"publisher","first-page":"795","DOI":"10.1007\/s00500-008-0352-6","article-title":"Use of biased neighborhood structures in multiobjective memetic algorithms","volume":"13","author":"Ishibuchi","year":"2009","journal-title":"Soft Computing"},{"key":"2024060313545278300_B27","first-page":"424","article-title":"Benchmark problem generators and results for the multiobjective degree-constrained minimum spanning tree problem","volume-title":"Genetic and Evolutionary Computation Conference","author":"Knowles","year":"2001"},{"key":"2024060313545278300_B28","first-page":"544","article-title":"A comparison of encodings and algorithms for multiobjective minimum spanning tree problems","volume":"1","author":"Knowles","year":"2001","journal-title":"Congress on Evolutionary Computation"},{"issue":"1","key":"2024060313545278300_B29","doi-asserted-by":"publisher","first-page":"48","DOI":"10.1090\/S0002-9939-1956-0078686-7","article-title":"On the shortest spanning subtree of a graph and the traveling salesman problem","volume":"7","author":"Kruskal","year":"1956","journal-title":"Proceedings of the American Mathematical Society"},{"issue":"10","key":"2024060313545278300_B30","doi-asserted-by":"publisher","DOI":"10.21105\/joss.00135","article-title":"batchtools: Tools for r to work on batch systems","volume":"2","author":"Lang","year":"2017","journal-title":"The Journal of Open Source Software"},{"issue":"8","key":"2024060313545278300_B31","doi-asserted-by":"publisher","first-page":"805","DOI":"10.1109\/42.876306","article-title":"A fast implementation of the minimum spanning tree method for phase unwrapping","volume":"19","author":"Li An","year":"2000","journal-title":"IEEE Transactions on Medical Imaging"},{"issue":"2","key":"2024060313545278300_B32","doi-asserted-by":"publisher","first-page":"357","DOI":"10.1016\/j.ejor.2007.06.032","article-title":"On solving multiobjective bin packing problems using evolutionary particle swarm optimization","volume":"190","author":"Liu","year":"2008","journal-title":"European Journal of Operational Research"},{"key":"2024060313545278300_B33","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4615-5563-6","volume-title":"Nonlinear multiobjective optimization","author":"Miettinen","year":"1998"},{"issue":"6","key":"2024060313545278300_B34","doi-asserted-by":"publisher","first-page":"1389","DOI":"10.1002\/j.1538-7305.1957.tb01515.x","article-title":"Shortest connection networks and some generalizations","volume":"36","author":"Prim","year":"1957","journal-title":"Bell System Technical Journal"},{"key":"2024060313545278300_B35","first-page":"142","article-title":"Neuer Beweis eines Satzes \u00fcber Permutationen","volume":"27","author":"Pr\u00fcfer","year":"1918","journal-title":"Archiv f\u00fcr Mathematik und Physik"},{"key":"2024060313545278300_B36","author":"R Core Team","year":"2021","journal-title":"R: A language and environment for statistical computing"},{"issue":"2","key":"2024060313545278300_B37","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1109\/TEVC.2006.871251","article-title":"Biased mutation operators for subgraph selection problems","volume":"10","author":"Raidl","year":"2006","journal-title":"IEEE Transactions on Evolutionary Computation"},{"key":"2024060313545278300_B38","first-page":"104","article-title":"Algorithmics of large and complex networks","volume-title":"A survey on multiple objective minimum spanning tree problems","author":"Ruzika","year":"2009"},{"key":"2024060313545278300_B39","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1016\/j.cor.2018.05.007","article-title":"A new approach for the multiobjective minimum spanning tree","volume":"98","author":"Santos","year":"2018","journal-title":"Computers & Operations Research"},{"issue":"4","key":"2024060313545278300_B40","doi-asserted-by":"crossref","first-page":"504","DOI":"10.1109\/TEVC.2011.2161872","article-title":"Using the averaged Hausdorff distance as a performance measure in evolutionary multiobjective optimization","volume":"16","author":"Sch\u00fctze","year":"2012","journal-title":"IEEE Transactions on Evolutionary Computation"},{"issue":"3","key":"2024060313545278300_B41","doi-asserted-by":"publisher","first-page":"472","DOI":"10.1287\/ijoc.1070.0260","article-title":"A multiobjective branch-and-bound framework: Application to the biobjective spanning tree problem","volume":"20","author":"Sourd","year":"2008","journal-title":"INFORMS Journal of Computing"},{"issue":"3","key":"2024060313545278300_B42","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1162\/evco.1994.2.3.221","article-title":"Multiobjective optimization using nondominated sorting in genetic algorithms","volume":"2","author":"Srinivas","year":"1994","journal-title":"Evolutionary Computation"},{"issue":"2","key":"2024060313545278300_B43","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1145\/321879.321884","article-title":"Efficiency of a good but not linear set union algorithm","volume":"22","author":"Tarjan","year":"1975","journal-title":"Journal of the ACM"},{"issue":"4","key":"2024060313545278300_B44","doi-asserted-by":"publisher","first-page":"690","DOI":"10.1145\/322154.322161","article-title":"Applications of path compression on balanced trees","volume":"26","author":"Tarjan","year":"1979","journal-title":"Journal of the ACM"},{"issue":"1","key":"2024060313545278300_B45","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1016\/S0377-2217(98)00016-2","article-title":"Genetic algorithm approach on multi-criteria minimum spanning tree problem","volume":"114","author":"Zhou","year":"1999","journal-title":"European Journal of Operational Research"},{"issue":"2","key":"2024060313545278300_B46","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1109\/TEVC.2003.810758","article-title":"Performance assessment of multiobjective optimizers: An analysis and review","volume":"7","author":"Zitzler","year":"2003","journal-title":"IEEE Transactions on Evolutionary Computation"}],"container-title":["Evolutionary Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/direct.mit.edu\/evco\/article-pdf\/32\/2\/143\/2372852\/evco_a_00335.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/direct.mit.edu\/evco\/article-pdf\/32\/2\/143\/2372852\/evco_a_00335.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,6,3]],"date-time":"2024-06-03T13:55:26Z","timestamp":1717422926000},"score":1,"resource":{"primary":{"URL":"https:\/\/direct.mit.edu\/evco\/article\/32\/2\/143\/116315\/On-Single-Objective-Sub-Graph-Based-Mutation-for"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024]]},"references-count":46,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2024,6,3]]},"published-print":{"date-parts":[[2024,6,3]]}},"URL":"https:\/\/doi.org\/10.1162\/evco_a_00335","relation":{},"ISSN":["1530-9304"],"issn-type":[{"value":"1530-9304","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2024]]},"published":{"date-parts":[[2024]]}}}