{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T12:18:34Z","timestamp":1759666714975,"version":"3.37.3"},"reference-count":18,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2018,1,15]],"date-time":"2018-01-15T00:00:00Z","timestamp":1515974400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"name":"Grant-in-Aid for Scientific Research of the Ministry of Education, Science, Sports and Culture of Japan","award":["24500023"],"award-info":[{"award-number":["24500023"]}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["61373048"],"award-info":[{"award-number":["61373048"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"name":"General Research Fund","award":["CityU 123013"],"award-info":[{"award-number":["CityU 123013"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2018,4]]},"DOI":"10.1007\/s10878-017-0245-7","type":"journal-article","created":{"date-parts":[[2018,1,14]],"date-time":"2018-01-14T23:20:43Z","timestamp":1515972043000},"page":"955-979","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["An approximation algorithm for maximum internal spanning tree"],"prefix":"10.1007","volume":"35","author":[{"given":"Zhi-Zhong","family":"Chen","sequence":"first","affiliation":[]},{"given":"Youta","family":"Harada","sequence":"additional","affiliation":[]},{"given":"Fei","family":"Guo","sequence":"additional","affiliation":[]},{"given":"Lusheng","family":"Wang","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2018,1,15]]},"reference":[{"issue":"1","key":"245_CR1","doi-asserted-by":"publisher","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 (2013) Exact and parameterized algorithms for max internal spanning tree. Algorithmica 65(1):95\u2013128","journal-title":"Algorithmica"},{"key":"245_CR2","unstructured":"Chen ZZ, Lin G, Wang L, Chen Y (2016) Approximation algorithms for the maximum weight internal spanning tree problem. CoRR. \n                    arxiv:abs\/1608.03299"},{"key":"245_CR3","first-page":"650","volume":"76","author":"N Coben","year":"2010","unstructured":"Coben N, Fomin FV, Gutin G, Kim EJ, Saurabh S, Yeo A (2010) Algorithm for finding k-vertex out-trees and its application to \n                    \n                      \n                    \n                    $$k$$\n                    \n                      \n                        k\n                      \n                    \n                  -internal out-branching problem. JCSS 76:650\u2013662","journal-title":"JCSS"},{"key":"245_CR4","doi-asserted-by":"publisher","first-page":"692","DOI":"10.1007\/s00453-011-9555-9","volume":"63","author":"FV Fomin","year":"2012","unstructured":"Fomin FV, Lokshtanov D, Grandoni F, Saurabh S (2012) Sharp separation and applications to exact and parameterized algorithms. Algorithmica 63:692\u2013706","journal-title":"Algorithmica"},{"key":"245_CR5","first-page":"1","volume":"79","author":"FV Fomin","year":"2013","unstructured":"Fomin FV, Gaspers S, Saurabh S, Thomasse S (2013) A linear vertex kernel for maximum internal spanning tree. JCSS 79:1\u20136","journal-title":"JCSS"},{"key":"245_CR6","volume-title":"Computers and intractability: a guide to the theory of NP-completeness","author":"MR Garey","year":"1979","unstructured":"Garey MR, Johnson DS (1979) Computers and intractability: a guide to the theory of NP-completeness. W.H. Freeman, New York"},{"key":"245_CR7","unstructured":"Hartvigsen D (1984) Extensions of matching theory. Ph.D. Thesis, Carnegie-Mellon University"},{"key":"245_CR8","doi-asserted-by":"crossref","unstructured":"Knauer M, Spoerhase J (2009) Better approximation algorithms for the maximum internal spanning tree problem. In: Proceedings of WADS, LNCS, vol 5664, pp 459\u2013470","DOI":"10.1007\/978-3-642-03367-4_40"},{"key":"245_CR9","doi-asserted-by":"crossref","unstructured":"Li X, Zhu D (2014) Approximating the maximum internal spanning tree problem via a maximum path-cycle cover. In: Proceedings of ISAAC, LNCS, vol 8889, pp 467\u2013478. CoRR. \n                    arxiv:abs\/1409.3700","DOI":"10.1007\/978-3-319-13075-0_37"},{"key":"245_CR10","unstructured":"Li W, Chen J, Wang J (2014) Deeper local search for better approximation on maximum internal spanning tree. In: Proceedings of ESA, LNCS, vol 8737, pp 642\u2013653"},{"key":"245_CR11","doi-asserted-by":"crossref","unstructured":"Li W, Wang J, Chen J, Cao Y (2015) A \n                    \n                      \n                    \n                    $$2k$$\n                    \n                      \n                        \n                          2\n                          k\n                        \n                      \n                    \n                  -vertex kernel for maximum internal spanning tree. In: Proceedings of WADS, LNCS, vol 9214, pp 495\u2013505","DOI":"10.1007\/978-3-319-21840-3_41"},{"key":"245_CR12","doi-asserted-by":"crossref","unstructured":"Li X, Feng H, Jiang H, Zhu B (2016) A polynomial time algorithm for finding a spanning tree with maximum number of internal vertices on interval graphs. In: Proceedings of FAW, LNCS, vol 9711, pp 92\u2013101","DOI":"10.1007\/978-3-319-39817-4_10"},{"key":"245_CR13","unstructured":"Prieto E (2005) Systematic kernelization in FPT algorithm design. Ph.D. Thesis, The University of Newcastle, Australia"},{"key":"245_CR14","doi-asserted-by":"crossref","unstructured":"Prieto E, Sliper C (2003) Either\/or: using vertex cover structure in designing FPT-algorithms\u2014the case of \n                    \n                      \n                    \n                    $$k$$\n                    \n                      \n                        k\n                      \n                    \n                  -internal spanning tree. In: Proceedings of WADS, LNCS, vol 2748, pp 474\u2013483","DOI":"10.1007\/978-3-540-45078-8_41"},{"key":"245_CR15","first-page":"308","volume":"12","author":"E Prieto","year":"2005","unstructured":"Prieto E, Sloper C (2005) Reducing to independent set structure\u2014the case of \n                    \n                      \n                    \n                    $$k$$\n                    \n                      \n                        k\n                      \n                    \n                  -internal spanning tree. Nord J Comput 12:308\u2013318","journal-title":"Nord J Comput"},{"issue":"50","key":"245_CR16","doi-asserted-by":"publisher","first-page":"5273","DOI":"10.1016\/j.tcs.2009.08.029","volume":"410","author":"G Salamon","year":"2009","unstructured":"Salamon G (2009a) Approximating the maximum internal spanning tree problem. Theor Comput Sci 410(50):5273\u20135284","journal-title":"Theor Comput Sci"},{"key":"245_CR17","unstructured":"Salamon G (2009b) Degree-based spanning tree optimization. Ph.D. thesis, Budapest University of Technology and Economics, Hungary"},{"issue":"5","key":"245_CR18","doi-asserted-by":"publisher","first-page":"164","DOI":"10.1016\/j.ipl.2007.08.030","volume":"105","author":"G Salamon","year":"2008","unstructured":"Salamon G, Wiener G (2008) On finding spanning trees with few leaves. Inf Process Lett 105(5):164\u2013169","journal-title":"Inf Process Lett"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10878-017-0245-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-017-0245-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-017-0245-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,1,14]],"date-time":"2019-01-14T20:29:43Z","timestamp":1547497783000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10878-017-0245-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,1,15]]},"references-count":18,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2018,4]]}},"alternative-id":["245"],"URL":"https:\/\/doi.org\/10.1007\/s10878-017-0245-7","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"type":"print","value":"1382-6905"},{"type":"electronic","value":"1573-2886"}],"subject":[],"published":{"date-parts":[[2018,1,15]]},"assertion":[{"value":"15 January 2018","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}