Minimum spanning trees made easier via multi-objective optimization

Many real-world problems are multi-objective optimization problems and evolutionary algorithms are quite successful on such problems. Since the task is to compute or approximate the Pareto front, multi-objective optimization problems are considered as more difficult than single-objective problems. One should not forget that the fitness vector with respect to more than one objective contains more information that in principle can direct the search of evolutionary algorithms. Therefore, it is possible that a single-objective problem can be solved more efficiently via a generalized multi-objective model of the problem. That this is indeed the case is proved by investigating the computation of minimum spanning trees.This work was supported by the Deutsche Forschungsgemeinschaft (DFG) as part of the Collaborative Research Center Computational Intelligence (SFB 531) and by the German-Israeli Foundation (GIF) in the project Robustness Aspects of Algorithms.