On the analysis of the (1+1) evolutionary algorithm for the maximum leaf spanning tree problem

References

• T. Bäck, Evolutionary Algorithms in Theory and Practice: Evolution Strategies, Evolutionary Programming, Genetic Algorithms, Oxford University Press, Oxford, 1996.
   Google Scholar
• J.R. Correa, C.G. Fernandes, M. Matamala, and Y. Wakabayashi, A 5/3-approximation for finding spanning trees with many leaves in cubic graphs, in 5th Proceedings of the Workshop on Approximation and Online Algorithms (WAOA), Lecture Notes in Computer Science, Vol. 4927, Springer, Berlin, 2008, pp. 184–192.
   Google Scholar
• S. Droste, T. Jansen, and I. Wegener, On the analysis of the (1+1) evolutionary algorithm, Theor. Comput. Sci. 276 (2002), pp. 51–81. doi: 10.1016/S0304-3975(01)00182-7
   Web of Science ®Google Scholar
• V. Estivill-Castro, M.R. Fellows, M.A. Langston, and F.A. Rosamond, FPT is P-time extremal structure I, in Proceedings of the 1st Workshop on Algorithms and Complexity in Durham (ACiD), H. Broersma, M. Johnson, and S. Szeider, eds., King's College, London, 2005, pp. 1–41.
   Google Scholar
• M.R. Fellows, D. Lokshtanov, N. Misra, M. Mnich, F.A. Rosamond, and S. Saurabh, The complexity ecology of parameters: An illustration using bounded max leaf number, Theory Comput. Syst. 45 (2009), pp. 822–848. doi: 10.1007/s00224-009-9167-9
   Web of Science ®Google Scholar
• T. Friedrich, J. He, N. Hebbinghaus, F. Neumann, and C. Witt, Analyses of simple hybrid evolutionary algorithms for the vertex cover problem, Evol. Comput. 17 (2009), pp. 3–20. doi: 10.1162/evco.2009.17.1.3
   PubMed Web of Science ®Google Scholar
• T. Fujie, An exact algorithm for the maximum leaf spanning tree problem, Comput. Oper. Res. 30 (2003), pp. 1931–1944. doi: 10.1016/S0305-0548(02)00117-X
   Web of Science ®Google Scholar
• M.R. Garey and D.S. Johnson, Computers and intractability: A guide to the theory of NP-completeness, W. H. Freeman and Company, New York, 1979.
   Google Scholar
• J.R. Griggs, D.J. Kleitman, and A. Shastri, Spanning trees with many leaves in cubic graphs, J. Graph. Theory. 13 (1989), pp. 669–695. doi: 10.1002/jgt.3190130604
   Web of Science ®Google Scholar
• S. Guha and S. Khuller, Approximation algorithms for connected dominating sets, in Proceedings of the Fourth Annual European Symposium on Algorithms, J. Díaz and M.J. Serna, eds., Springer, Barcelona, 1996, pp. 179–193.
   Google Scholar
• S. Kratsch, P.K. Lehre, F. Neumann, and P.S. Oliveto, Fixed parameter evolutionary algorithms and maximum leaf spanning trees: A matter of mutation, in Proceedings of Parallel Problem Solving from Nature-(PPSN XI), Lecture Notes in Computer Science, Vol. 6238, R. Schaefer, C. Cotta, J. Kołodziej, and G. Rudolph, eds., Springer, Berlin, 2011, pp. 204–213.
   Google Scholar
• P. Lemke, The Maximum-leaf Spanning Tree Problem in Cubic Graphs is NP-complete, IMA publication no. 428, University of Minnesota, Mineapolis, 1988.
   Google Scholar
• B. Li and M. Toulouse, Variations of the maximum leaf spanning tree problem for bipartite graphs, Inform. Process. Lett. 97 (2006), pp. 129–132. doi: 10.1016/j.ipl.2005.10.011
   Web of Science ®Google Scholar
• K. Loryś and G. Zwoźniak, Approximation algorithm for the maximum leaf spanning tree problem for cubic graphs, in ESA 2002, R.H. Möhring and R. Raman, eds., Lecture Notes in Computer Science, Vol. 2461, Springer, Heidelberg, 2002, pp. 686–697.
   Google Scholar
• H.-I. Lu and R. Ravi, The power of local optimization: Approximation algorithms for maximum-leaf spanning tree, in Proceedings of the Thirtieth Annual Allerton Conference on Communication, Control and Computing, P.V. Dooren and M. Spong, eds., Coordinated Science Laboratory, University of Illinois, Urbana-Champaign, October, 1992, pp. 533–542.
   Google Scholar
• H.-I. Lu and R. Ravi, The power of local optimizations: Approximation algorithms for maximum-leaf spanning tree (DRAFT)*, Tech. Rep. CS–96–05, Brown University, Providence, RI, 1996.
   Google Scholar
• H.-I. Lu and R. Ravi, A near-linear-time approximation algorithm for maximum-leaf spanning tree, Tech. Rep. CS–96–06, Brown University, Providence, RI, 1996.
   Google Scholar
• H.-I. Lu and R. Ravi, Approximating maximum leaf spanning trees in almost linear time, J. Algorithms. 29 (1998), pp. 132–141. doi: 10.1006/jagm.1998.0944
   Web of Science ®Google Scholar
• F. Neumann and I. Wegener, Randomized local search, evolutionary algorithms, and the minimum spanning tree problem, Theor. Comput. Sci. 378 (2007), pp. 32–40. doi: 10.1016/j.tcs.2006.11.002
   Web of Science ®Google Scholar
• F. Neumann and C. Witt, Bioinspired Computation in Combinatorial Optimization – Algorithms and Their Computational Complexity, Natural Computing Series, Springer, Berlin, 2010.
   Google Scholar
• P.S. Oliveto, J. He, and X. Yao, Analysis of the (1+1)-EA for finding approximate solutions to vertex cover problems, IEEE Trans. Evol. Comput. 13(5) (2009), pp. 1006–1029. doi: 10.1109/TEVC.2009.2014362
   Web of Science ®Google Scholar
• C. Payan, M. Tchuente, and N. H. Xuong, Arbres avec un nombres maximum de sommets pendants, Discret. Math. 49 (1984), pp. 267–273. doi: 10.1016/0012-365X(84)90163-8
   Web of Science ®Google Scholar
• G.R. Raidl and B.A. Julstrom, Edge sets: An effective evolutionary coding of spanning tree, IEEE Trans. Evol. Comput. 7 (2003), pp. 225–239. doi: 10.1109/TEVC.2002.807275
   Web of Science ®Google Scholar
• R. Solis-Oba, 2-approximation algorithm for finding a spanning tree with maximum number of leaves, in Proceeding of 6th ESA Symposium, Lecture Notes in Computer Science, Vol. 1461, G. Bilardi, A. Pietracaprina, G.F. Italiano, and G. Pucci, eds., Springer, Berlin, 1998, pp. 441–452.
   Google Scholar
• J.A. Storer, Constructing full spanning trees for cubic graphs, Inform. Process. Lett. 13 (1981), pp. 8–11. doi: 10.1016/0020-0190(81)90141-1
   Web of Science ®Google Scholar
• I. Wegener, Methods for the analysis of evolutionary algorithms on pseudo-boolean functions, in Evolutionary Optimization, R. Sarker, M. Mohammadian, and X. Yao, eds., Kluwer Academic Publishers, Dordrecht, 2002, pp. 349–369.
   Google Scholar
• C. Witt, Worst-case and average-case approximations by simple randomized search heuristics, in Proceedings of the 22nd Annual Symposium on Theoretical Aspects of Computer Science, Lecture Notes in Computer Science, Vol. 3404, V. Diekert and B. Durand, eds., Springer, Heidelberg, 2005, pp. 44–56.
   Google Scholar
• Y. Yu, X. Yao, and Z. Zhou, On the approximation ability of evolutionary optimization with application to minimum set cover, Artif. Intell. 180–181 (2012), pp. 20–33. doi: 10.1016/j.artint.2012.01.001
   Web of Science ®Google Scholar
• Y. Zhou, J. He, and Q. Nie, A comparative runtime analysis of heuristic algorithms for satisfiability problems, Artif. Intell. 173 (2009), pp. 240–257. doi: 10.1016/j.artint.2008.11.002
   PubMed Web of Science ®Google Scholar