{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T17:11:02Z","timestamp":1760202662069},"reference-count":11,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2013,8,30]],"date-time":"2013-08-30T00:00:00Z","timestamp":1377820800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2015,4]]},"DOI":"10.1007\/s00453-013-9827-7","type":"journal-article","created":{"date-parts":[[2013,8,29]],"date-time":"2013-08-29T15:52:08Z","timestamp":1377791528000},"page":"797-811","source":"Crossref","is-referenced-by-count":11,"title":["Better Approximation Algorithms for the Maximum Internal Spanning Tree Problem"],"prefix":"10.1007","volume":"71","author":[{"given":"Martin","family":"Knauer","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Joachim","family":"Spoerhase","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2013,8,30]]},"reference":[{"issue":"1","key":"9827_CR1","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1007\/s00453-011-9575-5","volume":"65","author":"D. Binkele-Raible","year":"2013","unstructured":"Binkele-Raible, D., Fernau, H., Gaspers, S., Liedloff, M.: Exact and parameterized algorithms for max internal spanning tree. Algorithmica 65(1), 95\u2013128 (2013)","journal-title":"Algorithmica"},{"key":"9827_CR2","first-page":"30","volume-title":"Proc. 10th International Workshop on Approximation and Online Algorithms (WAOA\u201912)","author":"M. Chimani","year":"2012","unstructured":"Chimani, M., Spoerhase, J.: Approximating spanning trees with few branches. In: Proc. 10th International Workshop on Approximation and Online Algorithms (WAOA\u201912), pp. 30\u201341 (2012)"},{"issue":"12","key":"9827_CR3","doi-asserted-by":"crossref","first-page":"2343","DOI":"10.1016\/j.disc.2007.04.071","volume":"308","author":"E. Flandrin","year":"2008","unstructured":"Flandrin, E., Kaiser, T., Kuzel, R., Li, H., Ryj\u00e1cek, Z.: Neighborhood unions and extremal spanning trees. Discrete Math. 308(12), 2343\u20132350 (2008)","journal-title":"Discrete Math."},{"issue":"1","key":"9827_CR4","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.jcss.2012.03.004","volume":"79","author":"F.V. Fomin","year":"2013","unstructured":"Fomin, F.V., Gaspers, S., Saurabh, S., Thomass\u00e9, S.: A linear vertex kernel for maximum internal spanning tree. J. Comput. Syst. Sci. 79(1), 1\u20136 (2013)","journal-title":"J. Comput. Syst. Sci."},{"key":"9827_CR5","doi-asserted-by":"crossref","first-page":"459","DOI":"10.1007\/978-3-642-03367-4_40","volume-title":"Proc. 11th Algorithms and Data Structures Symposium (WADS\u201909)","author":"M. Knauer","year":"2009","unstructured":"Knauer, M., Spoerhase, J.: Better approximation algorithms for the maximum internal spanning tree problem. In: Proc. 11th Algorithms and Data Structures Symposium (WADS\u201909), pp. 459\u2013470 (2009)"},{"key":"9827_CR6","first-page":"533","volume-title":"Proc. 30th Annual Allerton Conference on Communication, Control and Computing","author":"H.I. Lu","year":"1992","unstructured":"Lu, H.I., Ravi, R.: The power of local optimization: approximation algorithms for maximum-leaf spanning tree. In: Proc. 30th Annual Allerton Conference on Communication, Control and Computing, pp. 533\u2013542 (1992)"},{"issue":"5","key":"9827_CR7","doi-asserted-by":"crossref","first-page":"1201","DOI":"10.1137\/S0097539703431007","volume":"33","author":"J.B. Orlin","year":"2004","unstructured":"Orlin, J.B., Punnen, A.P., Schulz, A.S.: Approximate local search in combinatorial optimization. SIAM J. Comput. 33(5), 1201\u20131214 (2004)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"9827_CR8","first-page":"308","volume":"12","author":"E. Prieto","year":"2005","unstructured":"Prieto, E., Sloper, C.: Reducing to independent set structure\u2014the case of k-internal spanning tree. Nord. J. Comput. 12(3), 308\u2013318 (2005)","journal-title":"Nord. J. Comput."},{"issue":"50","key":"9827_CR9","doi-asserted-by":"crossref","first-page":"5273","DOI":"10.1016\/j.tcs.2009.08.029","volume":"410","author":"G. Salamon","year":"2009","unstructured":"Salamon, G.: Approximating the maximum internal spanning tree problem. Theor. Comput. Sci. 410(50), 5273\u20135284 (2009)","journal-title":"Theor. Comput. Sci."},{"key":"9827_CR10","doi-asserted-by":"crossref","first-page":"1209","DOI":"10.1016\/j.endm.2010.05.153","volume":"36","author":"G. Salamon","year":"2010","unstructured":"Salamon, G.: A survey on algorithms for the maximum internal spanning tree and related problems. Electron. Notes Discrete Math. 36, 1209\u20131216 (2010)","journal-title":"Electron. Notes Discrete Math."},{"key":"9827_CR11","doi-asserted-by":"crossref","first-page":"164","DOI":"10.1016\/j.ipl.2007.08.030","volume":"105","author":"G. Salamon","year":"2008","unstructured":"Salamon, G., Wiener, G.: On finding spanning trees with few leaves. Inf. Process. Lett. 105, 164\u2013169 (2008)","journal-title":"Inf. Process. Lett."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-013-9827-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-013-9827-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-013-9827-7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T13:45:12Z","timestamp":1559137512000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-013-9827-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,8,30]]},"references-count":11,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2015,4]]}},"alternative-id":["9827"],"URL":"https:\/\/doi.org\/10.1007\/s00453-013-9827-7","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,8,30]]}}}