{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,3]],"date-time":"2025-07-03T04:16:40Z","timestamp":1751516200081,"version":"3.41.0"},"publisher-location":"Cham","reference-count":15,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319774039"},{"type":"electronic","value":"9783319774046"}],"license":[{"start":{"date-parts":[[2018,1,1]],"date-time":"2018-01-01T00:00:00Z","timestamp":1514764800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2018]]},"DOI":"10.1007\/978-3-319-77404-6_16","type":"book-chapter","created":{"date-parts":[[2018,3,12]],"date-time":"2018-03-12T10:03:11Z","timestamp":1520848991000},"page":"201-216","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["A Tight Bound for Shortest Augmenting Paths on Trees"],"prefix":"10.1007","author":[{"given":"Bart\u0142omiej","family":"Bosek","sequence":"first","affiliation":[]},{"given":"Dariusz","family":"Leniowski","sequence":"additional","affiliation":[]},{"given":"Piotr","family":"Sankowski","sequence":"additional","affiliation":[]},{"given":"Anna","family":"Zych-Pawlewicz","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2018,3,13]]},"reference":[{"key":"16_CR1","doi-asserted-by":"crossref","unstructured":"Bernstein, A., Holm, J., Rotenberg, E.: Online bipartite matching with amortized $$O(\\log ^2 n)$$ replacements. arXiv:1707.06063 (2017)","DOI":"10.1137\/1.9781611975031.61"},{"key":"16_CR2","doi-asserted-by":"crossref","unstructured":"Bernstein, A., Stein, C.: Fully dynamic matching in bipartite graphs. In: ICALP, Part I, pp. 167\u2013179 (2015)","DOI":"10.1007\/978-3-662-47672-7_14"},{"issue":"1","key":"16_CR3","doi-asserted-by":"publisher","first-page":"80","DOI":"10.1145\/1360443.1360462","volume":"39","author":"BE Birnbaum","year":"2008","unstructured":"Birnbaum, B.E., Mathieu, C.: On-line bipartite matching made simple. SIGACT News 39(1), 80\u201387 (2008)","journal-title":"SIGACT News"},{"key":"16_CR4","doi-asserted-by":"crossref","unstructured":"Bosek, B., Leniowski, D., Sankowski, P., Zych, A.: Online bipartite matching in oine time. In: FOCS, pp. 384\u2013393 (2014)","DOI":"10.1109\/FOCS.2014.48"},{"key":"16_CR5","doi-asserted-by":"crossref","unstructured":"Bosek, B., Leniowski, D., Sankowski, P., Zych, A.: Shortest augmenting paths for online matchings on trees. In: WAOA, pp. 59\u201371 (2015)","DOI":"10.1007\/978-3-319-28684-6_6"},{"key":"16_CR6","doi-asserted-by":"crossref","unstructured":"Bosek, B., Leniowski, D., Sankowski, P., Zych-Pawlewicz, A.: A tight bound for shortest augmenting paths on trees. arXiv:1704.02093v2 (2017)","DOI":"10.1007\/978-3-319-77404-6_16"},{"key":"16_CR7","doi-asserted-by":"crossref","unstructured":"Chaudhuri, K., Daskalakis, C., Kleinberg, R.D., Lin, H.: Online bipartite perfect matching with augmentations. In: INFOCOM, pp. 1044\u20131052 (2009)","DOI":"10.1109\/INFCOM.2009.5062016"},{"key":"16_CR8","doi-asserted-by":"crossref","unstructured":"Devanur, N.R., Jain, K., Kleinberg, R.D.: Randomized primal-dual analysis of RANKING for online bipartite matching. In: SODA, pp. 101\u2013107 (2013)","DOI":"10.1137\/1.9781611973105.7"},{"issue":"2","key":"16_CR9","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":"16_CR10","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.) WADS 1995. LNCS, vol. 955, pp. 194\u2013205. Springer, Heidelberg (1995). https:\/\/doi.org\/10.1007\/3-540-60220-8_62"},{"key":"16_CR11","doi-asserted-by":"crossref","unstructured":"Gupta, A., Kumar, A., Stein, C.: Maintaining assignments online: matching, scheduling, and flows. In: SODA, pp. 468\u2013479 (2014)","DOI":"10.1137\/1.9781611973402.35"},{"key":"16_CR12","doi-asserted-by":"crossref","unstructured":"Gupta, M., Peng, R.: Fully dynamic ($$1\\!+\\!\\varepsilon $$)-approximate matchings. In: FOCS, pp. 548\u2013557 (2013)","DOI":"10.1109\/FOCS.2013.65"},{"key":"16_CR13","doi-asserted-by":"crossref","unstructured":"Karp, R.M., Vazirani, U.V., Vazirani, V.V.: An optimal algorithm for on-line bipartite matching. In: STOC, pp. 352\u2013358 (1990)","DOI":"10.1145\/100216.100262"},{"key":"16_CR14","doi-asserted-by":"crossref","unstructured":"Neiman, O., Solomon, S.: Simple deterministic algorithms for fully dynamic maximal matching. In: STOC, pp. 745\u2013754 (2013)","DOI":"10.1145\/2488608.2488703"},{"key":"16_CR15","unstructured":"Sankowski, P.: Faster dynamic matchings and vertex connectivity. In: SODA, pp. 118\u2013126 (2007)"}],"container-title":["Lecture Notes in Computer Science","LATIN 2018: Theoretical Informatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-77404-6_16","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,2]],"date-time":"2025-07-02T18:29:19Z","timestamp":1751480959000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-77404-6_16"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018]]},"ISBN":["9783319774039","9783319774046"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-77404-6_16","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2018]]},"assertion":[{"value":"13 March 2018","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"LATIN","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Latin American Symposium on Theoretical Informatics","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Buenos Aires","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Argentina","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2018","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"16 April 2018","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"19 April 2018","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"13","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"latin2018","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/latin2018.dc.uba.ar\/#","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}