{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,31]],"date-time":"2025-12-31T00:58:52Z","timestamp":1767142732502,"version":"build-2238731810"},"reference-count":24,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2021,4,6]],"date-time":"2021-04-06T00:00:00Z","timestamp":1617667200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,4,6]],"date-time":"2021-04-06T00:00:00Z","timestamp":1617667200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Sci. China Inf. Sci."],"published-print":{"date-parts":[[2021,5]]},"DOI":"10.1007\/s11432-019-2630-2","type":"journal-article","created":{"date-parts":[[2021,4,12]],"date-time":"2021-04-12T03:02:55Z","timestamp":1618196575000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Incremental algorithms for the maximum internal spanning tree problem"],"prefix":"10.1007","volume":"64","author":[{"given":"Xianbin","family":"Zhu","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wenjun","family":"Li","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yongjie","family":"Yang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jianxin","family":"Wang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,4,6]]},"reference":[{"key":"2630_CR1","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M R Garey","year":"1979","unstructured":"Garey M R, Johnson D S. Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: WH Freeman & Co, 1979"},{"key":"2630_CR2","doi-asserted-by":"publisher","first-page":"955","DOI":"10.1007\/s10878-017-0245-7","volume":"35","author":"Z Z Chen","year":"2018","unstructured":"Chen Z Z, Harada Y, Guo F, et al. An approximation algorithm for maximum internal spanning tree. J Comb Optim, 2018, 35: 955\u2013979","journal-title":"J Comb Optim"},{"key":"2630_CR3","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3","volume-title":"Parameterized Algorithms","author":"M Cygan","year":"2015","unstructured":"Cygan M, Fomin F V, Kowalik L, et al. Parameterized Algorithms. Berlin: Springer, 2015"},{"key":"2630_CR4","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized Complexity","author":"R G Downey","year":"1999","unstructured":"Downey R G, Fellows M R. Parameterized Complexity. Berlin: Springer, 1999"},{"key":"2630_CR5","unstructured":"Fomin F V, Golovach P A, Simonov K. Parameterized k-clustering: the distance matters! 2019. ArXiv:1902.08559"},{"key":"2630_CR6","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1016\/j.tcs.2018.04.020","volume":"786","author":"W J Li","year":"2019","unstructured":"Li W J, Liu H Y, Wang J X, et al. An improved linear kernel for complementary maximal strip recovery: simpler and smaller. Theory Comput Sci, 2019, 786: 55\u201366","journal-title":"Theory Comput Sci"},{"key":"2630_CR7","doi-asserted-by":"publisher","first-page":"28","DOI":"10.1016\/j.jcss.2018.03.002","volume":"97","author":"F Shi","year":"2018","unstructured":"Shi F, Chen J E, Feng Q L, et al. A parameterized algorithm for the maximum agreement forest problem on multiple rooted multifurcating trees. J Comput Syst Sci, 2018, 97: 28\u201344","journal-title":"J Comput Syst Sci"},{"key":"2630_CR8","doi-asserted-by":"publisher","first-page":"3320","DOI":"10.1109\/TMC.2017.2696009","volume":"16","author":"L K Guo","year":"2017","unstructured":"Guo L K, Shen H, Zhu W X. Efficient approximation algorithms for multi-antennae largest weight data retrieval. IEEE Trans Mobile Comput, 2017, 16: 3320\u20133333","journal-title":"IEEE Trans Mobile Comput"},{"key":"2630_CR9","doi-asserted-by":"publisher","first-page":"1091","DOI":"10.1007\/s10878-018-0340-4","volume":"37","author":"Q L Feng","year":"2019","unstructured":"Feng Q L, Hu J X, Huang N, et al. Improved PTAS for the constrained k-means problem. J Comb Optim, 2019, 37: 1091\u20131110","journal-title":"J Comb Optim"},{"key":"2630_CR10","doi-asserted-by":"publisher","unstructured":"Feng Q L, Zhu S M, Wang J X. An improved kernel for max-bisection above tight lower bound. Theory Comput Sci, 2018. doi: https:\/\/doi.org\/10.1016\/j.tcs.2018.06.027","DOI":"10.1016\/j.tcs.2018.06.027"},{"key":"2630_CR11","volume-title":"Kernelization: Theory of Parameterized Preprocessing","author":"F V Fomin","year":"2019","unstructured":"Fomin F V, Lokshtanov D, Saurabh S, et al. Kernelization: Theory of Parameterized Preprocessing. Cambridge: Cambridge University Press, 2019"},{"key":"2630_CR12","doi-asserted-by":"crossref","unstructured":"Prieto E, Sloper C. Either\/or: using vertex cover structure in designing FPT-algorithms \u2014 the case of k-internal spanning tree. In: Proceedings of the 8th International Workshop on Algorithms and Data Structures (WADS), Ottawa, 2003. 474\u2013483","DOI":"10.1007\/978-3-540-45078-8_41"},{"key":"2630_CR13","first-page":"308","volume":"12","author":"E Prieto","year":"2005","unstructured":"Prieto E, Sloper C. Reducing to independent set structure: the case of k-internal spanning tree. Nord J Comput, 2005, 12: 308\u2013318","journal-title":"Nord J Comput"},{"key":"2630_CR14","doi-asserted-by":"publisher","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, et al. A linear vertex kernel for maximum internal spanning tree. J Comput Syst Sci, 2013, 79: 1\u20136","journal-title":"J Comput Syst Sci"},{"key":"2630_CR15","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1016\/j.ic.2016.11.003","volume":"252","author":"W J Li","year":"2017","unstructured":"Li W J, Cao Y X, Chen J E, et al. Deeper local search for parameterized and approximation algorithms for maximum internal spanning tree. Inf Comput, 2017, 252: 187\u2013200","journal-title":"Inf Comput"},{"key":"2630_CR16","doi-asserted-by":"crossref","unstructured":"Li X F, Zhu D M. Approximating the maximum internal spanning tree problem via a maximum path-cycle cover. In: Proceedings of the 25th International Symposium on Algorithms and Computation (ISAAC), Jeonju, 2014. 467\u2013478","DOI":"10.1007\/978-3-319-13075-0_37"},{"key":"2630_CR17","doi-asserted-by":"publisher","first-page":"797","DOI":"10.1007\/s00453-013-9827-7","volume":"71","author":"M Knauer","year":"2015","unstructured":"Knauer M, Spoerhase J. Better approximation algorithms for the maximum internal spanning tree problem. Algorithmica, 2015, 71: 797\u2013811","journal-title":"Algorithmica"},{"key":"2630_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. On finding spanning trees with few leaves. Inf Process Lett, 2008, 105: 164\u2013169","journal-title":"Inf Process Lett"},{"key":"2630_CR19","series-title":"Dissertation for Ph.D. Degree","volume-title":"Incremental algorithms: solving problems in a changing world","author":"A M Sharp","year":"2007","unstructured":"Sharp A M. Incremental algorithms: solving problems in a changing world. Dissertation for Ph.D. Degree. Ithaca: Cornell University, 2007"},{"key":"2630_CR20","doi-asserted-by":"publisher","first-page":"816","DOI":"10.1137\/S0097539701383443","volume":"32","author":"R R Mettu","year":"2003","unstructured":"Mettu R R, Plaxton C G. The online median problem. SIAM J Comput, 2003, 32: 816\u2013832","journal-title":"SIAM J Comput"},{"key":"2630_CR21","doi-asserted-by":"publisher","first-page":"3633","DOI":"10.1137\/070698257","volume":"39","author":"G L Lin","year":"2010","unstructured":"Lin G L, Nagarajan C, Rajaraman R, et al. A general approach for incremental approximation and hierarchical clustering. SIAM J Comput, 2010, 39: 3633\u20133669","journal-title":"SIAM J Comput"},{"key":"2630_CR22","unstructured":"Bernstein A, Disser Y, Gro\u00df M. General bounds for incremental maximization. In: Proceedings of the 44th International Colloquium on Automata, Languages, and Programming (ICALP), Warsaw, 2017"},{"key":"2630_CR23","doi-asserted-by":"crossref","unstructured":"Blum A, Chalasani P, Coppersmith D, et al. The minimum latency problem. In: Proceedings of the 26th Annual ACM Symposium on Theory of Computing (STOC), Montreal, 1994. 163\u2013171","DOI":"10.1145\/195058.195125"},{"key":"2630_CR24","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1016\/j.ipl.2003.12.001","volume":"89","author":"B Codenotti","year":"2004","unstructured":"Codenotti B, de Marco G, Leoncini M, et al. Approximation algorithms for a hierarchically structured bin packing problem. Inf Process Lett, 2004, 89: 215\u2013221","journal-title":"Inf Process Lett"}],"updated-by":[{"DOI":"10.1007\/s11432-022-3525-7","type":"erratum","label":"Erratum","source":"publisher","updated":{"date-parts":[[2022,9,26]],"date-time":"2022-09-26T00:00:00Z","timestamp":1664150400000}}],"container-title":["Science China Information Sciences"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11432-019-2630-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11432-019-2630-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11432-019-2630-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,10,11]],"date-time":"2022-10-11T07:52:02Z","timestamp":1665474722000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11432-019-2630-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,4,6]]},"references-count":24,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2021,5]]}},"alternative-id":["2630"],"URL":"https:\/\/doi.org\/10.1007\/s11432-019-2630-2","relation":{},"ISSN":["1674-733X","1869-1919"],"issn-type":[{"value":"1674-733X","type":"print"},{"value":"1869-1919","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,4,6]]},"assertion":[{"value":"20 January 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 June 2019","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 July 2019","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 April 2021","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 September 2022","order":5,"name":"change_date","label":"Change Date","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"Erratum","order":6,"name":"change_type","label":"Change Type","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"An Erratum to this paper has been published:","order":7,"name":"change_details","label":"Change Details","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"https:\/\/doi.org\/10.1007\/s11432-022-3525-7","URL":"https:\/\/doi.org\/10.1007\/s11432-022-3525-7","order":8,"name":"change_details","label":"Change Details","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"152103"}}