{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,3,29]],"date-time":"2022-03-29T10:29:42Z","timestamp":1648549782972},"reference-count":16,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2018,1,24]],"date-time":"2018-01-24T00:00:00Z","timestamp":1516752000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100004281","name":"Narodowe Centrum Nauki","doi-asserted-by":"publisher","award":["2013\/11\/D\/ST6\/03100"],"award-info":[{"award-number":["2013\/11\/D\/ST6\/03100"]}],"id":[{"id":"10.13039\/501100004281","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004281","name":"Narodowe Centrum Nauki","doi-asserted-by":"publisher","award":["2013\/11\/D\/ST6\/03100"],"award-info":[{"award-number":["2013\/11\/D\/ST6\/03100"]}],"id":[{"id":"10.13039\/501100004281","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004281","name":"Narodowe Centrum Nauki","doi-asserted-by":"publisher","award":["2013\/11\/D\/ST6\/03100"],"award-info":[{"award-number":["2013\/11\/D\/ST6\/03100"]}],"id":[{"id":"10.13039\/501100004281","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004281","name":"Narodowe Centrum Nauki","doi-asserted-by":"publisher","award":["2013\/11\/D\/ST6\/03100"],"award-info":[{"award-number":["2013\/11\/D\/ST6\/03100"]}],"id":[{"id":"10.13039\/501100004281","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["677651"],"award-info":[{"award-number":["677651"]}],"id":[{"id":"10.13039\/501100000781","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":[[2018,2]]},"DOI":"10.1007\/s00224-017-9838-x","type":"journal-article","created":{"date-parts":[[2018,1,24]],"date-time":"2018-01-24T00:59:25Z","timestamp":1516755565000},"page":"337-348","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Shortest Augmenting Paths for Online Matchings on Trees"],"prefix":"10.1007","volume":"62","author":[{"given":"Bart\u0142omiej","family":"Bosek","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dariusz","family":"Leniowski","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Piotr","family":"Sankowski","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Anna","family":"Zych-Pawlewicz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2018,1,24]]},"reference":[{"key":"9838_CR1","doi-asserted-by":"crossref","unstructured":"Baswana, S., Gupta, M., Sandeep, S.: Fully dynamic maximal matching in O(N) update time. In: Proceedings of the 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS \u201911, pp. 383\u2013392. IEEE Computer Society, Washington, DC (2011)","DOI":"10.1109\/FOCS.2011.89"},{"key":"9838_CR2","doi-asserted-by":"crossref","unstructured":"Bernstein, A., Stein, C.: Fully dynamic matching in bipartite graphs. 2015 to appear at ICALP (2015)","DOI":"10.1007\/978-3-662-47672-7_14"},{"key":"9838_CR3","doi-asserted-by":"crossref","unstructured":"Bosek, B., Leniowski, D., Sankowski, P., Zych, A.: Online Bipartite Matching in Offline Time. In: 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, pp. 384\u2013393. IEEE Computer Society, Philadelphia (2014)","DOI":"10.1109\/FOCS.2014.48"},{"key":"9838_CR4","doi-asserted-by":"crossref","unstructured":"Chaudhuri, K., Daskalakis, C., Kleinberg, R.D., Lin, H.: Online bipartite perfect matching with augmentations. In: 28th IEEE International Conference on Computer Communications, Joint Conference of the IEEE Computer and Communications Societies INFOCOM 2009, pp. 1044\u20131052. IEEE, Rio De Janeiro (2009)","DOI":"10.1109\/INFCOM.2009.5062016"},{"issue":"2","key":"9838_CR5","doi-asserted-by":"publisher","first-page":"248","DOI":"10.1145\/321694.321699","volume":"19","author":"J Edmonds","year":"1972","unstructured":"Edmonds, J., Karp, R.M.: Theoretical improvements in algorithmic efficiency for network flow problems. J. ACM 19(2), 248\u2013264 (1972)","journal-title":"J. ACM"},{"key":"9838_CR6","doi-asserted-by":"crossref","unstructured":"Grove, E.F., Kao, M.-Y., Krishnan, P., Vitter, J.S.: Online perfect matching and mobile computing. In: Akl, S.G., Dehne, F., Sack, J.-R., Santoro, N. (eds.) Algorithms and Data Structures, volume 955 of Lecture Notes in Computer Science, pp. 194\u2013205. Springer, Berlin (1995)","DOI":"10.1007\/3-540-60220-8_62"},{"key":"9838_CR7","doi-asserted-by":"crossref","unstructured":"Gupta, A., Kumar, A., Stein, C.: Maintaining assignments online: matching, scheduling, and flows. In: Chekuri, C. (ed.) Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, pp. 468\u2013479. SIAM, Portland (2014)","DOI":"10.1137\/1.9781611973402.35"},{"key":"9838_CR8","doi-asserted-by":"crossref","unstructured":"Gupta, M., Peng, R.: Fully dynamic (1 + e)-approximate matchings. In: 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, vol. 0, pp. 548\u2013557 (2013)","DOI":"10.1109\/FOCS.2013.65"},{"key":"9838_CR9","doi-asserted-by":"crossref","unstructured":"Ivkovi\u0107, Z., Lloyd, E.L.: Fully dynamic maintenance of vertex cover. In: Leeuwen, J. (ed.) Graph-Theoretic Concepts in Computer Science, volume 790 of Lecture Notes in Computer Science, pp. 99\u2013111. Springer, Berlin (1994)","DOI":"10.1007\/3-540-57899-4_44"},{"issue":"1","key":"9838_CR10","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1007\/BF02579407","volume":"6","author":"RM Karp","year":"1986","unstructured":"Karp, R.M., Upfal, E., Wigderson, A.: Constructing a perfect matching is in random nc. Combinatorica 6(1), 35\u201348 (1986)","journal-title":"Combinatorica"},{"key":"9838_CR11","unstructured":"Leniowski, D.: On Maintaining Online Bipartite Matchings with Augmentations. PhD thesis, University of Warsaw (2015)"},{"key":"9838_CR12","doi-asserted-by":"crossref","unstructured":"Mehta, A., Saberi, A., Vazirani, U.V., Vazirani, V.V.: Adwords and Generalized On-Line Matching. In: 46Th Annual IEEE Symposium on Foundations of Computer Science FOCS 2005, pp. 264\u2013273 (2005)","DOI":"10.1109\/SFCS.2005.12"},{"key":"9838_CR13","doi-asserted-by":"crossref","unstructured":"Neiman, O., Solomon, S.: Simple deterministic algorithms for fully dynamic maximal matching. In: Proceedings of the Forty-fifth Annual ACM Symposium on Theory of Computing, STOC \u201913, pp. 745\u2013754. ACM, New York (2013)","DOI":"10.1145\/2488608.2488703"},{"key":"9838_CR14","first-page":"341","volume-title":"Property Testing. Chapter Dynamic Approximate Vertex Cover and Maximum Matching","author":"K Onak","year":"2010","unstructured":"Onak, K., Rubinfeld, R.: Property Testing. Chapter Dynamic Approximate Vertex Cover and Maximum Matching, pp. 341\u2013345. Springer, Berlin (2010)"},{"key":"9838_CR15","unstructured":"Sankowski, P.: Faster dynamic matchings and vertex connectivity. In: Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 07, pp. 118-126. Society for Industrial and Applied Mathematics, Philadelphia (2007)"},{"issue":"3","key":"9838_CR16","doi-asserted-by":"publisher","first-page":"362","DOI":"10.1016\/0022-0000(83)90006-5","volume":"26","author":"DD Sleator","year":"1983","unstructured":"Sleator, D.D., Tarjan, R.E.: A data structure for dynamic trees. J. Comput. Syst. Sci. 26(3), 362\u2013391 (1983)","journal-title":"J. Comput. Syst. Sci."}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-017-9838-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-017-9838-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-017-9838-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,10,9]],"date-time":"2019-10-09T14:45:54Z","timestamp":1570632354000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-017-9838-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,1,24]]},"references-count":16,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2018,2]]}},"alternative-id":["9838"],"URL":"https:\/\/doi.org\/10.1007\/s00224-017-9838-x","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,1,24]]},"assertion":[{"value":"24 January 2018","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}