{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,28]],"date-time":"2025-03-28T04:50:23Z","timestamp":1743137423616,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662490136"},{"type":"electronic","value":"9783662490143"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-662-49014-3_45","type":"book-chapter","created":{"date-parts":[[2015,12,23]],"date-time":"2015-12-23T09:41:36Z","timestamp":1450863696000},"page":"505-512","source":"Crossref","is-referenced-by-count":2,"title":["Approximation Performance of the (1+1) Evolutionary Algorithm for the Minimum Degree Spanning Tree Problem"],"prefix":"10.1007","author":[{"given":"Xiaoyun","family":"Xia","sequence":"first","affiliation":[]},{"given":"Yuren","family":"Zhou","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2015,12,24]]},"reference":[{"key":"45_CR1","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, San Francisco (1979)"},{"key":"45_CR2","unstructured":"F\u00fcrer, M., Raghavachari, B.: An NC approximation algorithm for the minimum degree spanning tree problem. In: Proceedings of the 28th Annual Allerton Conference on Communication, Control and Computing, pp. 274\u2013281 (1990)"},{"key":"45_CR3","unstructured":"F\u00fcrer, M., Raghavachari, B.: Approximating the minimum degree spanning tree to within one from the optimal degree. In: Proceedings of the 3rd Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 317\u2013324. ACM, USA (1992)"},{"key":"45_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1007\/3-540-56287-7_112","volume-title":"Foundations of Software Technology and Theoretical Computer Science","author":"R Ravi","year":"1992","unstructured":"Ravi, R., Raghavachari, B., Klein, P.: Approximation through local optimality: designing networks with small degree. In: Shyamasundar, R.K. (ed.) FSTTCS 1992. LNCS, vol. 652, pp. 279\u2013290. Springer, Heidelberg (1992)"},{"key":"45_CR5","doi-asserted-by":"publisher","first-page":"409","DOI":"10.1006\/jagm.1994.1042","volume":"17","author":"M F\u00fcrer","year":"1994","unstructured":"F\u00fcrer, M., Raghavachari, B.: Approximating the minimum-degree steiner tree to within one of optimal. J. Algorithms 17, 409\u2013423 (1994)","journal-title":"J. Algorithms"},{"issue":"7\u20138","key":"45_CR6","doi-asserted-by":"publisher","first-page":"1229","DOI":"10.1016\/0098-3004(94)90072-8","volume":"20","author":"K Gallagher","year":"1994","unstructured":"Gallagher, K., Sambridge, M.: Genetic algorithms: a powerful tool for large-scale non-linear optimization problems. Comput. Geosci. 20(7\u20138), 1229\u20131236 (1994)","journal-title":"Comput. Geosci."},{"key":"45_CR7","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1016\/S0304-3975(01)00182-7","volume":"276","author":"S Droste","year":"2002","unstructured":"Droste, S., Jansen, T., Wegener, I.: On the analysis of the (1+1) evolutionary algorithm. Theor. Comput. Sci. 276, 51\u201381 (2002)","journal-title":"Theor. Comput. Sci."},{"key":"45_CR8","series-title":"Natural Computing Series","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-17339-4","volume-title":"Analyzing Evolutionary Algorithms - The Computer Science Perspective","author":"T Jansen","year":"2013","unstructured":"Jansen, T.: Analyzing Evolutionary Algorithms - The Computer Science Perspective. Natural Computing Series. Springer, Heidelberg (2013)"},{"issue":"1","key":"45_CR9","doi-asserted-by":"publisher","first-page":"32","DOI":"10.1016\/j.tcs.2006.11.002","volume":"378","author":"F Neumann","year":"2007","unstructured":"Neumann, F., Wegener, I.: Randomized local search, evolutionary algorithms, and the minimum spanning tree problem. Theor. Comput. Sci. 378(1), 32\u201340 (2007)","journal-title":"Theor. Comput. Sci."},{"key":"45_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"44","DOI":"10.1007\/978-3-540-31856-9_4","volume-title":"STACS 2005","author":"C Witt","year":"2005","unstructured":"Witt, C.: Worst-case and average-case approximations by simple randomized search heuristics. In: Diekert, V., Durand, B. (eds.) STACS 2005. LNCS, vol. 3404, pp. 44\u201356. Springer, Heidelberg (2005)"},{"key":"45_CR11","doi-asserted-by":"publisher","first-page":"20","DOI":"10.1016\/j.artint.2012.01.001","volume":"180\u2013181","author":"Y Yu","year":"2012","unstructured":"Yu, Y., Yao, X., Zhou, Z.: On the approximation ability of evolutionary optimization with application to minimum set cover. Artif. Intell. 180\u2013181, 20\u201333 (2012)","journal-title":"Artif. Intell."},{"issue":"10","key":"45_CR12","doi-asserted-by":"publisher","first-page":"2023","DOI":"10.1080\/00207160.2014.964695","volume":"92","author":"X Xia","year":"2015","unstructured":"Xia, X., Zhou, Y., Lai, X.: On the analysis of the (1+1) evolutionary algorithm for the maximum leaf spanning tree problem. Int. J. Comput. Math. 92(10), 2023\u20132035 (2015)","journal-title":"Int. J. Comput. Math."},{"issue":"3","key":"45_CR13","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1109\/TEVC.2002.807275","volume":"7","author":"GR Raidl","year":"2003","unstructured":"Raidl, G.R., Julstrom, B.A.: Edge sets: an effective evolutionary coding of spanning tree. IEEE Trans. Evol. Comput. 7(3), 225\u2013239 (2003)","journal-title":"IEEE Trans. Evol. Comput."},{"issue":"99","key":"45_CR14","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1109\/TEVC.2014.2378512","volume":"PP","author":"X Zhang","year":"2014","unstructured":"Zhang, X., Tian, Y., Jin, Y.: A knee point driven evolutionary algorithm for many-objective optimization. IEEE Trans. Evol. Comput. PP(99), 1 (2014). doi:\n                  10.1109\/TEVC.2014.2378512","journal-title":"IEEE Trans. Evol. Comput."},{"issue":"2","key":"45_CR15","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1109\/TEVC.2014.2308305","volume":"19","author":"X Zhang","year":"2015","unstructured":"Zhang, X., Tian, Y., Cheng, R., Jin, Y.: An efficient approach to non-dominated sorting for evolutionary multi-objective optimization. IEEE Trans. Evol. Comput. 19(2), 201\u2013213 (2015)","journal-title":"IEEE Trans. Evol. Comput."},{"key":"45_CR16","doi-asserted-by":"publisher","first-page":"54","DOI":"10.1016\/j.tcs.2011.02.016","volume":"436","author":"T Chen","year":"2012","unstructured":"Chen, T., Tang, K., Chen, G., Yao, X.: A large population size can be unhelpful in evolutionary algorithms. Theor. Comput. Sci. 436, 54\u201370 (2012)","journal-title":"Theor. Comput. Sci."},{"key":"45_CR17","doi-asserted-by":"publisher","first-page":"673","DOI":"10.1007\/s00453-012-9622-x","volume":"64","author":"B Doerr","year":"2012","unstructured":"Doerr, B., Johannsen, D., Winzen, C.: Multiplicative drift analysis. Algorithmica 64, 673\u2013697 (2012)","journal-title":"Algorithmica"}],"container-title":["Communications in Computer and Information Science","Bio-Inspired Computing -- Theories and Applications"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-49014-3_45","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,31]],"date-time":"2019-05-31T22:57:00Z","timestamp":1559343420000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-49014-3_45"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783662490136","9783662490143"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-49014-3_45","relation":{},"ISSN":["1865-0929","1865-0937"],"issn-type":[{"type":"print","value":"1865-0929"},{"type":"electronic","value":"1865-0937"}],"subject":[],"published":{"date-parts":[[2015]]}}}