{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,7,28]],"date-time":"2024-07-28T19:10:59Z","timestamp":1722193859295},"reference-count":24,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2019,7,24]],"date-time":"2019-07-24T00:00:00Z","timestamp":1563926400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2019,7,24]],"date-time":"2019-07-24T00:00:00Z","timestamp":1563926400000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["11771013,61751303,11531011"],"award-info":[{"award-number":["11771013,61751303,11531011"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Zhejiang Provincial Natural Science Foundation of China","award":["LD19A010001","LY19A010018"],"award-info":[{"award-number":["LD19A010001","LY19A010018"]}]},{"DOI":"10.13039\/501100012226","name":"Fundamental Research Funds for the Central Universities","doi-asserted-by":"publisher","award":["lzujbky-2017-163"],"award-info":[{"award-number":["lzujbky-2017-163"]}],"id":[{"id":"10.13039\/501100012226","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2020,2]]},"DOI":"10.1007\/s00224-019-09944-w","type":"journal-article","created":{"date-parts":[[2019,7,24]],"date-time":"2019-07-24T10:55:07Z","timestamp":1563965707000},"page":"327-338","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Algorithm for Online 3-Path Vertex Cover"],"prefix":"10.1007","volume":"64","author":[{"given":"Yubai","family":"Zhang","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zhao","family":"Zhang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yishuo","family":"Shi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xianyue","family":"Li","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,7,24]]},"reference":[{"issue":"1\u20132","key":"9944_CR1","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/s10107-003-0436-0","volume":"97","author":"S Albers","year":"2003","unstructured":"Albers, S.: Online algorithms: a survey. Math. Program. 97(1\u20132), 3\u201326 (2003)","journal-title":"Math. Program."},{"issue":"9","key":"9944_CR2","doi-asserted-by":"publisher","first-page":"436","DOI":"10.1016\/j.ipl.2008.12.021","volume":"109","author":"E Birmel\u00e9","year":"2009","unstructured":"Birmel\u00e9, E., Delbot, F., Laforest, C.: Mean analysis of an online algorithm for the vertex cover problem. Inf. Process. Lett. 109(9), 436\u2013439 (2009)","journal-title":"Inf. Process. Lett."},{"issue":"3","key":"9944_CR3","first-page":"93","volume":"47","author":"J Boyar","year":"2016","unstructured":"Boyar, J., Favrholdt, L.M., Kudahl, C., Larsen, K.S., Mikkelsen, J.W.: Online algorithms with advice: a survey. ACM Comput. Surv. 47(3), 93\u2013129 (2016)","journal-title":"ACM Comput. Surv."},{"issue":"12","key":"9944_CR4","doi-asserted-by":"publisher","first-page":"1189","DOI":"10.1016\/j.dam.2011.04.008","volume":"159","author":"B Bre\u0161ar","year":"2011","unstructured":"Bre\u0161ar, B., Kardo\u0161, F., Katreni\u010d, J., Semani\u0161in, G.: Minimum k-path vertex cover. Discret. Appl. Math. 159(12), 1189\u20131195 (2011)","journal-title":"Discret. Appl. Math."},{"issue":"13","key":"9944_CR5","first-page":"983","volume":"30","author":"B Bre\u0161ar","year":"2014","unstructured":"Bre\u0161ar, B., Krivo\u0161-Bellu\u0161, R., Semani\u0161in, G., \u0160parl, P.: On the weighted k-path vertex cover problem. Comput. Aided Des. 30(13), 983\u2013989 (2014)","journal-title":"Comput. Aided Des."},{"key":"9944_CR6","unstructured":"Chang, M.S., Chen, L.H., Hung, L.J., Liu, Y.Z., Rossmanith, P., Sikdar, S.: An O\n\u2217(1.4658n)-time exact algorithm for the maximum bounded-degree-1 set problem. In: Proceedings of the 31st Workshop on Combinatorial Mathematics and Computation Theory, pp. 9\u201318 (2014)"},{"key":"9944_CR7","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1016\/j.disopt.2015.11.003","volume":"19","author":"MS Chang","year":"2016","unstructured":"Chang, M.S., Chen, L.H., Hung, L.J., Rossmanith, P., Su, P.C.: Fixed parameter algorithms for vertex cover P\n3. Discret. Optim. 19, 12\u201322 (2016)","journal-title":"Discret. Optim."},{"key":"9944_CR8","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1016\/j.cosrev.2016.12.001","volume":"24","author":"HI Christensen","year":"2017","unstructured":"Christensen, H.I., Khan, A., Pokutta, S., Tetali, P.: Approximation and online algorithms for multidimensional bin packing: a survey. Comput. Sci. Rev. 24, 63\u201379 (2017)","journal-title":"Comput. Sci. Rev."},{"key":"9944_CR9","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1016\/j.tcs.2004.08.015","volume":"332","author":"M Demange","year":"2005","unstructured":"Demange, M., Paschos, V.T.: On-line vertex-covering. Theor. Comput. Sci. 332, 83\u2013108 (2005)","journal-title":"Theor. Comput. Sci."},{"issue":"7","key":"9944_CR10","first-page":"845","volume":"129","author":"A Fiat","year":"1998","unstructured":"Fiat, A., Woeginger, G.: Online algorithms: the state of the art. Am. Soc. Civil Eng. 129(7), 845\u2013856 (1998)","journal-title":"Am. Soc. Civil Eng."},{"key":"9944_CR11","doi-asserted-by":"publisher","first-page":"213","DOI":"10.1016\/S0166-218X(98)00035-3","volume":"86","author":"T Fujito","year":"1998","unstructured":"Fujito, T.: A unified approximation algorithm for node-deletion problems. Discret. Appl. Math. 86, 213\u2013231 (1998)","journal-title":"Discret. Appl. Math."},{"key":"9944_CR12","unstructured":"Irani, S., Karlin, A.R.: Online computation. In: Approximation Algorithms for NP-Hard Problems, pp. 521\u2013564. PWS Publishing Company MA (1996)"},{"issue":"50","key":"9944_CR13","doi-asserted-by":"publisher","first-page":"7009","DOI":"10.1016\/j.tcs.2011.09.009","volume":"412","author":"F Kardo\u0161","year":"2011","unstructured":"Kardo\u0161, F., Katreni\u010d, J., Schiermeyer, I.: On computing the minimum 3-path vertex cover and dissociation number of graphs. Theor. Comput. Sci. 412(50), 7009\u20137017 (2011)","journal-title":"Theor. Comput. Sci."},{"issue":"4","key":"9944_CR14","doi-asserted-by":"publisher","first-page":"273","DOI":"10.1016\/j.ipl.2015.12.002","volume":"116","author":"J Katreni\u010d","year":"2016","unstructured":"Katreni\u010d, J.: A fast FPT algorithm for 3-path vertex cover. Inf. Process. Lett. 116(4), 273\u2013278 (2016)","journal-title":"Inf. Process. Lett."},{"issue":"10","key":"9944_CR15","doi-asserted-by":"publisher","first-page":"2103","DOI":"10.1080\/00207160.2014.881476","volume":"91","author":"Y Li","year":"2014","unstructured":"Li, Y., Tu, J.: A 2-approximation algorithm for the vertex cover P\n4 problem in cubic graphs. Int. J. Comput. Math. 91(10), 2103\u20132108 (2014)","journal-title":"Int. J. Comput. Math."},{"key":"9944_CR16","unstructured":"Mcmahan, H.B.: A survey of algorithms and analysis for adaptive online learning. Eprint Arxiv, pp. 61\u201366 (2015)"},{"key":"9944_CR17","doi-asserted-by":"publisher","first-page":"106","DOI":"10.1007\/978-3-642-12368-9_8","volume-title":"Information Security Theory and Practices. Security and Privacy of Pervasive Systems and Smart Devices","author":"Mari\u00e1n Novotn\u00fd","year":"2010","unstructured":"Novotn\u00fd, M.: Design and analysis of a generalized canvas protocol. In: Proceedings of WISTP 2010 LNCS 6033, pp. 106\u2013121 (2010)"},{"issue":"2","key":"9944_CR18","doi-asserted-by":"publisher","first-page":"202","DOI":"10.1145\/2786.2793","volume":"28","author":"DD Sleator","year":"1985","unstructured":"Sleator, D.D., Tarjan, R.E.: Amortized efficiency of list update and paging rules. Commun. ACM 28(2), 202\u2013208 (1985)","journal-title":"Commun. ACM"},{"issue":"2","key":"9944_CR19","doi-asserted-by":"publisher","first-page":"96","DOI":"10.1016\/j.ipl.2014.06.018","volume":"115","author":"JH Tu","year":"2015","unstructured":"Tu, J.H.: A fixed-parameter algorithm for the vertex cover P\n3 problem. Inf. Process. Lett. 115(2), 96\u201399 (2015)","journal-title":"Inf. Process. Lett."},{"issue":"13","key":"9944_CR20","doi-asserted-by":"publisher","first-page":"481","DOI":"10.1016\/j.ipl.2013.04.002","volume":"113","author":"JH Tu","year":"2013","unstructured":"Tu, J.H., Yang, F.: The vertex cover P\n3 problem in cubic graphs. Inf. Process. Lett. 113(13), 481\u2013485 (2013)","journal-title":"Inf. Process. Lett."},{"issue":"50","key":"9944_CR21","doi-asserted-by":"publisher","first-page":"7044","DOI":"10.1016\/j.tcs.2011.09.013","volume":"412","author":"JH Tu","year":"2011","unstructured":"Tu, J.H., Zhou, W.L.: A primal-dual approximation algorithm for the vertex cover P\n3 problem. Theor. Comput. Sci. 412(50), 7044\u20137048 (2011)","journal-title":"Theor. Comput. Sci."},{"issue":"14","key":"9944_CR22","doi-asserted-by":"publisher","first-page":"683","DOI":"10.1016\/j.ipl.2011.04.009","volume":"111","author":"JH Tu","year":"2011","unstructured":"Tu, J.H., Zhou, W.L.: A factor 2 approximation algorithm for the vertex cover P\n3 problem. Inf. Process. Lett. 111(14), 683\u2013686 (2011)","journal-title":"Inf. Process. Lett."},{"issue":"2","key":"9944_CR23","doi-asserted-by":"publisher","first-page":"414","DOI":"10.1007\/s10878-016-9999-6","volume":"34","author":"JH Tu","year":"2017","unstructured":"Tu, J.H., Wu, L.D., Yuan, J., Cui, L.: On the vertex cover P\n3 problem parameterized by treewidth. J. Comb. Optim. 34(2), 414\u2013425 (2017)","journal-title":"J. Comb. Optim."},{"key":"9944_CR24","first-page":"654","volume-title":"Lecture Notes in Computer Science","author":"Mingyu Xiao","year":"2017","unstructured":"Xiao, M.Y., Kou, S.W.: Kernalization and parameterized algorithms for 3-path vertex cover. In: Theory and Applications of Models of Computation LNCS 10185, pp. 654\u2013668 (2017)"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-019-09944-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-019-09944-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-019-09944-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,7,22]],"date-time":"2020-07-22T23:23:41Z","timestamp":1595460221000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-019-09944-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,7,24]]},"references-count":24,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2020,2]]}},"alternative-id":["9944"],"URL":"https:\/\/doi.org\/10.1007\/s00224-019-09944-w","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,7,24]]},"assertion":[{"value":"24 July 2019","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}