{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T05:05:37Z","timestamp":1743051937751,"version":"3.40.3"},"publisher-location":"Cham","reference-count":32,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783031095733"},{"type":"electronic","value":"9783031095740"}],"license":[{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"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":[],"published-print":{"date-parts":[[2022]]},"DOI":"10.1007\/978-3-031-09574-0_8","type":"book-chapter","created":{"date-parts":[[2022,6,23]],"date-time":"2022-06-23T17:36:07Z","timestamp":1656005767000},"page":"115-132","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Output Sensitive Fault Tolerant Maximum Matching"],"prefix":"10.1007","author":[{"given":"Niranka","family":"Banerjee","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Manoj","family":"Gupta","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Venkatesh","family":"Raman","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Saket","family":"Saurabh","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,6,24]]},"reference":[{"unstructured":"Assadi, S., Bernstein, A.: Towards a unified theory of sparsification for matching problems. In: 2nd Symposium on Simplicity in Algorithms, 8\u20139 January 2019 - San Diego, CA, USA, pages 11:1\u201311:20 (2019)","key":"8_CR1"},{"doi-asserted-by":"publisher","unstructured":"Assadi, S., Khanna, S., Li, Y.: The stochastic matching problem with (very) few queries. In: Proceedings of the 2016 ACM Conference on Economics and Computation, EC 2016, Maastricht, The Netherlands, 24\u201328 July 2016, pp. 43\u201360 (2016). https:\/\/doi.org\/10.1145\/2940716.2940769","key":"8_CR2","DOI":"10.1145\/2940716.2940769"},{"doi-asserted-by":"publisher","unstructured":"Assadi, S., Khanna, S., Li, Y.: The stochastic matching problem: beating half with a non-adaptive algorithm. In: Proceedings of the 2017 ACM Conference on Economics and Computation, EC 2017, Cambridge, MA, USA, 26\u201330 June 2017, pp. 99\u2013116 (2017). https:\/\/doi.org\/10.1145\/3033274.3085146","key":"8_CR3","DOI":"10.1145\/3033274.3085146"},{"doi-asserted-by":"crossref","unstructured":"Baswana, S., Chaudhury, S.R., Choudhary, K., Khan, S.: Dynamic DFS in undirected graphs: breaking the O(m) barrier. In: Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, 10\u201312 January 2016, pp. 730\u2013739 (2016)","key":"8_CR4","DOI":"10.1137\/1.9781611974331.ch52"},{"doi-asserted-by":"crossref","unstructured":"Baswana, S., Choudhary, K., Roditty, L.: Fault tolerant reachability for directed graphs. In: Proceedings of the 29th International Symposium on istributed Computing - DISC 2015, Tokyo, Japan, 7\u20139 October 2015, pp. 528\u2013543 (2015)","key":"8_CR5","DOI":"10.1007\/978-3-662-48653-5_35"},{"doi-asserted-by":"crossref","unstructured":"Behnezhad, S., Derakhshan, M., Hajiaghayi, M.: Stochastic matching with few queries: (1-$$\\epsilon $$) approximation. CoRR, abs\/2002.11880 (2020). https:\/\/arxiv.org\/abs\/2002.11880","key":"8_CR6","DOI":"10.1145\/3357713.3384340"},{"doi-asserted-by":"publisher","unstructured":"Behnezhad, S., Reyhani, N.: Almost optimal stochastic weighted matching with few queries. In: Proceedings of the 2018 ACM Conference on Economics and Computation, Ithaca, NY, USA, 18\u201322 June 2018, pp. 235\u2013249 (2018). https:\/\/doi.org\/10.1145\/3219166.3219226","key":"8_CR7","DOI":"10.1145\/3219166.3219226"},{"doi-asserted-by":"crossref","unstructured":"Bil\u00f2, D., Grandoni, F., Gual\u00e0, L., Leucci, S., Proietti, G.: Improved purely additive fault-tolerant spanners. In: Algorithms - ESA 2015\u201323rd Annual European Symposium, Patras, Greece, 14\u201316 September 2015, pp. 167\u2013178 (2015)","key":"8_CR8","DOI":"10.1007\/978-3-662-48350-3_15"},{"unstructured":"Bil\u00f2, D., Gual\u00e0, L., Leucci, S., Proietti, G.: Multiple-edge-fault-tolerant approximate shortest-path trees. In: 33rd Symposium on Theoretical Aspects of Computer Science, STACS 2016, 17\u201320 February 2016, Orl\u00e9ans, France, pp. 18:1\u201318:14 (2016)","key":"8_CR9"},{"issue":"1","key":"8_CR10","doi-asserted-by":"publisher","first-page":"16","DOI":"10.1287\/opre.2019.1856","volume":"68","author":"A Blum","year":"2020","unstructured":"Blum, A., Dickerson, J.P., Haghtalab, N., Procaccia, A.D., Sandholm, T., Sharma, A.: Ignorance is almost bliss: Near-optimal stochastic matching with few queries. Oper. Res. 68(1), 16\u201334 (2020). https:\/\/doi.org\/10.1287\/opre.2019.1856","journal-title":"Oper. Res."},{"key":"8_CR11","doi-asserted-by":"publisher","first-page":"94","DOI":"10.1016\/j.tcs.2015.02.036","volume":"580","author":"G Braunschvig","year":"2015","unstructured":"Braunschvig, G., Chechik, S., Peleg, D., Sealfon, A.: Fault tolerant additive and ($$\\mu $$, $$\\alpha $$)-spanners. Theor. Comput. Sci. 580, 94\u2013100 (2015)","journal-title":"Theor. Comput. Sci."},{"issue":"7","key":"8_CR12","doi-asserted-by":"publisher","first-page":"3403","DOI":"10.1137\/090758039","volume":"39","author":"S Chechik","year":"2010","unstructured":"Chechik, S., Langberg, M., Peleg, D., Roditty, L.: Fault tolerant spanners for general graphs. SIAM J. Comput. 39(7), 3403\u20133423 (2010)","journal-title":"SIAM J. Comput."},{"key":"8_CR13","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3","volume-title":"Parameterized Algorithms","author":"M Cygan","year":"2015","unstructured":"Cygan, M., et al.: Parameterized Algorithms. Springer, Cham (2015). https:\/\/doi.org\/10.1007\/978-3-319-21275-3"},{"doi-asserted-by":"crossref","unstructured":"Dinitz, M., Krauthgamer, R.: Fault-tolerant spanners: better and simpler. In: Proceedings of the 30th Annual ACM Symposium on Principles of Distributed Computing, PODC 2011, San Jose, CA, USA, 6\u20138 June 2011, pp. 169\u2013178 (2011)","key":"8_CR14","DOI":"10.1145\/1993806.1993830"},{"key":"8_CR15","doi-asserted-by":"publisher","first-page":"449","DOI":"10.4153\/CJM-1965-045-4","volume":"17","author":"J Edmonds","year":"1965","unstructured":"Edmonds, J.: Paths, trees, and flowers. Can. J. Math. 17, 449\u2013467 (1965)","journal-title":"Can. J. Math."},{"doi-asserted-by":"crossref","unstructured":"Fomin, F.V., Lokshtanov, D., Saurabh, S., Zehavi, M.: Kernelization: Theory of Parameterized Preprocessing. Cambridge University Press, Cambridge (2019)","key":"8_CR16","DOI":"10.1017\/9781107415157"},{"doi-asserted-by":"crossref","unstructured":"Gabow, H.N., Tarjan, R.E.: Faster scaling algorithms for general graph-matching problems. J. ACM 38(4), 815\u2013853 (1991)","key":"8_CR17","DOI":"10.1145\/115234.115366"},{"doi-asserted-by":"publisher","unstructured":"Gupta, M., Khan, S.: Multiple source dual fault tolerant BFS trees. In: Chatzigiannakis, I., Indyk, P., Kuhn, F., Muscholl, A. (eds.) 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017, 10\u201314 July 2017, Warsaw, Poland, volume 80 of LIPIcs, pp. 127:1\u2013127:15. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2017). https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2017.127","key":"8_CR18","DOI":"10.4230\/LIPIcs.ICALP.2017.127"},{"doi-asserted-by":"publisher","unstructured":"Gupta, M., Peng, R.: Fully dynamic (1+ e)-approximate matchings. In: 54th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2013, 26\u201329 October 2013, Berkeley, CA, USA, pp. 548\u2013557. IEEE Computer Society (2013). https:\/\/doi.org\/10.1109\/FOCS.2013.65","key":"8_CR19","DOI":"10.1109\/FOCS.2013.65"},{"issue":"4","key":"8_CR20","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1137\/0202019","volume":"2","author":"JE Hopcroft","year":"1973","unstructured":"Hopcroft, J.E., Karp, R.M.: An $$n^{5\/2}$$ algorithm for maximum matchings in bipartite graphs. SIAM J. Comput. 2(4), 225\u2013231 (1973)","journal-title":"SIAM J. Comput."},{"doi-asserted-by":"crossref","unstructured":"Huang, C.-C., Kavitha, T.: Efficient algorithms for maximum weight matchings in general graphs with small edge weights. In: SODA, pp. 1400\u20131412 (2012)","key":"8_CR21","DOI":"10.1137\/1.9781611973099.110"},{"key":"8_CR22","volume-title":"Combinatorial Optimization: Networks and Matroids","author":"E Lawler","year":"1976","unstructured":"Lawler, E.: Combinatorial Optimization: Networks and Matroids. Holt Rinehart & Winston, Newyork (1976)"},{"key":"8_CR23","volume-title":"Matching Theory","author":"L Lovasz","year":"1986","unstructured":"Lovasz, L., Plummer, M.D.: Matching Theory. AMS Chelsea Publishing, Amsterdam (1986)"},{"doi-asserted-by":"crossref","unstructured":"Micali, S., Vazirani, V.V.: An $$O(\\sqrt{(|V|)} |E|)$$ algorithm for finding maximum matching in general graphs. In: FOCS, pp. 17\u201327 (1980)","key":"8_CR24","DOI":"10.1109\/SFCS.1980.12"},{"issue":"6","key":"8_CR25","doi-asserted-by":"publisher","first-page":"1329","DOI":"10.1145\/195613.195663","volume":"41","author":"R Motwani","year":"1994","unstructured":"Motwani, R.: Average-case analysis of algorithms for matchings and related problems. J. ACM 41(6), 1329\u20131356 (1994)","journal-title":"J. ACM"},{"doi-asserted-by":"crossref","unstructured":"Mucha, M., Sankowski, P.: Maximum matchings via Gaussian elimination. In: FOCS, pp. 248\u2013255 (2004)","key":"8_CR26","DOI":"10.1007\/978-3-540-30140-0_48"},{"doi-asserted-by":"crossref","unstructured":"Parter, M.: Vertex fault tolerant additive spanners. In: Distributed Computing - 28th International Symposium, DISC 2014, Austin, TX, USA, 12\u201315 October 2014, pp. 167\u2013181 (2014)","key":"8_CR27","DOI":"10.1007\/978-3-662-45174-8_12"},{"doi-asserted-by":"crossref","unstructured":"Parter, M.: Dual failure resilient BFS structure. In: Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing, PODC 2015, Donostia-San Sebasti\u00e1n, Spain, 21\u201323 July 2015, pp. 481\u2013490 (2015)","key":"8_CR28","DOI":"10.1145\/2767386.2767408"},{"doi-asserted-by":"crossref","unstructured":"Parter, M., Peleg, D.: Sparse fault-tolerant BFS trees. In: Algorithms - ESA 2013\u201321st Annual European Symposium, Sophia Antipolis, France, 2\u20134 September 2013, pp. 779\u2013790 (2013)","key":"8_CR29","DOI":"10.1007\/978-3-642-40450-4_66"},{"doi-asserted-by":"crossref","unstructured":"Parter, M., Peleg, D.: Fault tolerant approximate BFS structures. In: Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, 5\u20137 January 2014, pp. 1073\u20131092 (2014)","key":"8_CR30","DOI":"10.1137\/1.9781611973402.80"},{"doi-asserted-by":"crossref","unstructured":"Thomass\u00e9, S.: A 4k$${}^{\\text{2}}$$ kernel for feedback vertex set. ACM Trans. Algorithms 6(2), 32:1\u201332:8 (2010)","key":"8_CR31","DOI":"10.1145\/1721837.1721848"},{"doi-asserted-by":"publisher","unstructured":"Yamaguchi, Y., Maehara, T.: Stochastic packing integer programs with few queries. In: Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, 7\u201310 January 2018, pp. 293\u2013310 (2018). https:\/\/doi.org\/10.1137\/1.9781611975031.21","key":"8_CR32","DOI":"10.1137\/1.9781611975031.21"}],"container-title":["Lecture Notes in Computer Science","Computer Science \u2013 Theory and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-09574-0_8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,27]],"date-time":"2024-09-27T17:16:44Z","timestamp":1727457404000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-09574-0_8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022]]},"ISBN":["9783031095733","9783031095740"],"references-count":32,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-09574-0_8","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2022]]},"assertion":[{"value":"24 June 2022","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"CSR","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Computer Science Symposium in Russia","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"St. Petersburg","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Russia","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2022","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"29 June 2022","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"3 July 2022","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"17","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"csr2022","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/logic.pdmi.ras.ru\/csr2022\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Easychair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"51","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"21","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"41% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"7","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}