Randomized Search Heuristics and the Minimum Spanning Tree Problem

We show that evolutionary algorithms find minimum spanning trees in expected polynomial time without employing the global technique of greedy algorithms. After that we take a multi-objective view on the problem. Usually multi-objective optimization problems are considered as more difficult than single-objective problems. But 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.
We show that the single-objective problem of computing minimum spanning trees can be solved more efficiently via a generalized multi-objective model.