Revised analysis of the (1+1) EA for the minimum spanning tree problem

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review


We revisit the classical analysis of the (1+1) EA for the minimum spanning tree problem in the case that nothing is known about the weights of the underlying graph. Here the original upper bound on the expected running time by Neumann and Wegener [Theor. Comput. Sci. 378(1), 32-40, 2007], which depends on the largest weight of the graph, is of no use. The best upper bound available before in this case is due to Reichel and Skutella [FOGA 2009, 21-28] and is of order O(m3 \log n), where m is the number of edges and n the number of vertices. Using an adaptive drift analysis, we show the improved bound O(m2 (sqrt{c(G)} + \log n)), where c(G) is the circumference (length of the longest cycle) of the graph. This is only by an asymptotic factor of at most sqrt{n}/\log n away from the classical lower bound. Furthermore, an alternative fitness function leading to the bound O(m2\log n) is proposed, and limitations of the adaptive drift analysis are pointed out.
Original languageEnglish
Title of host publicationProceedings of the 2014 conference on Genetic and evolutionary computation (GECCO '14)
PublisherAssociation for Computing Machinery
Publication date2014
ISBN (Electronic)978-1-4503-2662-9
Publication statusPublished - 2014
Event2014 Genetic and Evolutionary Computation Conference - Vancouver, Canada
Duration: 12 Jul 201416 Jul 2014


Conference2014 Genetic and Evolutionary Computation Conference
Internet address


  • Evolutionary Algorithms
  • Minimum Spanning Tree Problem
  • Runtime Analysis


Dive into the research topics of 'Revised analysis of the (1+1) EA for the minimum spanning tree problem'. Together they form a unique fingerprint.

Cite this