{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,13]],"date-time":"2026-01-13T06:36:40Z","timestamp":1768286200324,"version":"3.49.0"},"publisher-location":"Cham","reference-count":15,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783319286839","type":"print"},{"value":"9783319286846","type":"electronic"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-319-28684-6_6","type":"book-chapter","created":{"date-parts":[[2016,1,12]],"date-time":"2016-01-12T10:32:03Z","timestamp":1452594723000},"page":"59-71","source":"Crossref","is-referenced-by-count":2,"title":["Shortest Augmenting Paths for Online Matchings on Trees"],"prefix":"10.1007","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","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,1,13]]},"reference":[{"key":"6_CR1","doi-asserted-by":"crossref","unstructured":"Baswana, S., Gupta, M., Sen, S.: Fully dynamic maximal matching in $${O}(\\log n)$$ O ( log n ) update time. In: Proceedings of the 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011, ppp. 383\u2013392. IEEE Computer Society, Washington, DC, USA (2011)","DOI":"10.1109\/FOCS.2011.89"},{"key":"6_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1007\/978-3-662-47672-7_14","volume-title":"Automata, Languages, and Programming","author":"A Bernstein","year":"2015","unstructured":"Bernstein, A., Stein, C.: Fully dynamic matching in bipartite graphs. In: Halld\u00f3rsson, M.M., Iwama, K., Kobayashi, N., Speckmann, B. (eds.) ICALP 2015. LNCS, vol. 9134, pp. 167\u2013179. Springer, Heidelberg (2015)"},{"key":"6_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, Philadelphia, PA, USA, 18\u201321 October 2014, pp. 384\u2013393. IEEE Computer Society (2014)","DOI":"10.1109\/FOCS.2014.48"},{"key":"6_CR4","doi-asserted-by":"crossref","unstructured":"Chaudhuri, K., Daskalakis, C., Kleinberg, R.D., Lin, H.: Online bipartite perfect matching with augmentations. In: INFOCOM 2009, 28th IEEE International Conference on Computer Communications, Joint Conference of the IEEE Computer and Communications Societies, 19\u201325 April 2009, Rio de Janeiro, Brazil, pp. 1044\u20131052. IEEE (2009)","DOI":"10.1109\/INFCOM.2009.5062016"},{"issue":"2","key":"6_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":"6_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"194","DOI":"10.1007\/3-540-60220-8_62","volume-title":"Algorithms and Data Structures","author":"EF Grove","year":"1995","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. Lecture Notes in Computer Science, vol. 955, pp. 194\u2013205. Springer, Heidelberg (1995)"},{"key":"6_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, Portland, Oregon, USA, 5\u20137 January 2014, pp. 468\u2013479. SIAM (2014)","DOI":"10.1137\/1.9781611973402.35"},{"key":"6_CR8","doi-asserted-by":"crossref","unstructured":"Gupta, M., Peng, R.: Fully dynamic $$(1+e)$$ ( 1 + e ) -approximate matchings. In: IEEE 54th Annual Symposium on Foundations of Computer. Science, pp 548\u2013557 (2013)","DOI":"10.1109\/FOCS.2013.65"},{"key":"6_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1007\/3-540-57899-4_44","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"Z Ivkovi\u0107","year":"1994","unstructured":"Ivkovi\u0107, Z., Lloyd, E.L.: Fully dynamic maintenance of vertex cover. In: Leeuwen, J. (ed.) Graph-Theoretic Concepts in Computer Science. Lecture Notes in Computer Science, vol. 790, pp. 99\u2013111. Springer, Heidelberg (1994)"},{"issue":"1","key":"6_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":"6_CR11","doi-asserted-by":"crossref","unstructured":"Mehta, A., Saberi, A., Vazirani, U., Vazirani, V.: Adwords and generalized on-line matching. In: 46th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2005, pp. 264\u2013273, October 2005","DOI":"10.1109\/SFCS.2005.12"},{"key":"6_CR12","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 2013, pp. 745\u2013754. ACM, New York, NY, USA (2013)","DOI":"10.1145\/2488608.2488703"},{"key":"6_CR13","doi-asserted-by":"publisher","first-page":"341","DOI":"10.1007\/978-3-642-16367-8_28","volume-title":"Property Testing","author":"K Onak","year":"2010","unstructured":"Onak, K., Rubinfeld, R.: Dynamic approximate vertex cover and maximum matching. In: Goldreich, O. (ed.) Property Testing, vol. 6390, pp. 341\u2013345. Springer, Heidelberg (2010)"},{"key":"6_CR14","unstructured":"Sankowski, P.: Faster dynamic matchings and vertex connectivity. In: Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007, pp. 118\u2013126. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA (2007)"},{"issue":"3","key":"6_CR15","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":["Lecture Notes in Computer Science","Approximation and Online Algorithms"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-28684-6_6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,1]],"date-time":"2025-06-01T03:25:28Z","timestamp":1748748328000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-28684-6_6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319286839","9783319286846"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-28684-6_6","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015]]}}}