{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,23]],"date-time":"2025-06-23T16:05:32Z","timestamp":1750694732286},"publisher-location":"Cham","reference-count":15,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319592497"},{"type":"electronic","value":"9783319592503"}],"license":[{"start":{"date-parts":[[2017,1,1]],"date-time":"2017-01-01T00:00:00Z","timestamp":1483228800000},"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":[[2017]]},"DOI":"10.1007\/978-3-319-59250-3_8","type":"book-chapter","created":{"date-parts":[[2017,5,23]],"date-time":"2017-05-23T09:04:39Z","timestamp":1495530279000},"page":"86-98","source":"Crossref","is-referenced-by-count":18,"title":["Deterministic Fully Dynamic Approximate Vertex Cover and Fractional Matching in O(1) Amortized Update Time"],"prefix":"10.1007","author":[{"given":"Sayan","family":"Bhattacharya","sequence":"first","affiliation":[]},{"given":"Deeparnab","family":"Chakrabarty","sequence":"additional","affiliation":[]},{"given":"Monika","family":"Henzinger","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,5,24]]},"reference":[{"key":"8_CR1","doi-asserted-by":"crossref","unstructured":"Abboud, A., Williams, V.V.: Popular conjectures imply strong lower bounds for dynamic problems. In: FOCS (2014)","DOI":"10.1109\/FOCS.2014.53"},{"key":"8_CR2","doi-asserted-by":"crossref","unstructured":"Baswana, S., Gupta, M., Sen, S.: Fully dynamic maximal matching in $$O(\\log n)$$ update time. In: FOCS (2011)","DOI":"10.1109\/FOCS.2011.89"},{"key":"8_CR3","doi-asserted-by":"crossref","unstructured":"Bernstein, A., Stein, C.: Faster fully dynamic matchings with small approximation ratios. In: SODA (2016)","DOI":"10.1137\/1.9781611974331.ch50"},{"key":"8_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"206","DOI":"10.1007\/978-3-662-47672-7_17","volume-title":"Automata, Languages, and Programming","author":"S Bhattacharya","year":"2015","unstructured":"Bhattacharya, S., Henzinger, M., Italiano, G.F.: Design of dynamic algorithms via primal-dual method. In: Halld\u00f3rsson, M.M., Iwama, K., Kobayashi, N., Speckmann, B. (eds.) ICALP 2015. LNCS, vol. 9134, pp. 206\u2013218. Springer, Heidelberg (2015). doi: 10.1007\/978-3-662-47672-7_17"},{"key":"8_CR5","doi-asserted-by":"crossref","unstructured":"Bhattacharya, S., Henzinger, M., Italiano, G.F.: Deterministic fully dynamic data structures for vertex cover and matching. In: SODA (2015)","DOI":"10.1137\/1.9781611973730.54"},{"key":"8_CR6","doi-asserted-by":"crossref","unstructured":"Bhattacharya, S., Henzinger, M., Nanongkai, D.: New deterministic approximation algorithms for fully dynamic matching. In: STOC (2016)","DOI":"10.1145\/2897518.2897568"},{"key":"8_CR7","doi-asserted-by":"crossref","unstructured":"Gupta, A., Krishnaswamy, R., Kumar, A., Panigrahi, D.: Online and dynamic algorithms for set cover. In: STOC (2017)","DOI":"10.1145\/3055399.3055493"},{"key":"8_CR8","unstructured":"Gupta, M., Peng, R.: Fully dynamic $$(1+\\epsilon )$$ -approximate matchings. In: FOCS (2013)"},{"key":"8_CR9","doi-asserted-by":"crossref","unstructured":"Henzinger, M., Krinninger, S., Nanongkai, D., Saranurak, T.: Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture. In: STOC (2015)","DOI":"10.1145\/2746539.2746609"},{"issue":"3","key":"8_CR10","doi-asserted-by":"crossref","first-page":"351","DOI":"10.1007\/PL00009228","volume":"22","author":"MR Henzinger","year":"1998","unstructured":"Henzinger, M.R., Fredman, M.L.: Lower bounds for fully dynamic connectivity problems in graphs. Algorithmica 22(3), 351\u2013362 (1998)","journal-title":"Algorithmica"},{"key":"8_CR11","doi-asserted-by":"crossref","unstructured":"Neiman, O., Solomon, S.: Simple deterministic algorithms for fully dynamic maximal matching. In: STOC (2013)","DOI":"10.1145\/2488608.2488703"},{"key":"8_CR12","doi-asserted-by":"crossref","unstructured":"Onak, K., Rubinfeld, R.: Maintaining a large matching and a small vertex cover. In: STOC (2010)","DOI":"10.1145\/1806689.1806753"},{"key":"8_CR13","doi-asserted-by":"crossref","unstructured":"Patrascu, M.: Lower bounds for dynamic connectivity. In: Encyclopedia of Algorithms, pp. 1162\u20131167 (2016)","DOI":"10.1007\/978-1-4939-2864-4_214"},{"key":"8_CR14","unstructured":"Sankowski, P.: Faster dynamic matchings and vertex connectivity. In: SODA (2007)"},{"key":"8_CR15","doi-asserted-by":"crossref","unstructured":"Solomon, S.: Fully dynamic maximal matching in constant update time. In: FOCS (2016)","DOI":"10.1109\/FOCS.2016.43"}],"container-title":["Lecture Notes in Computer Science","Integer Programming and Combinatorial Optimization"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-59250-3_8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,24]],"date-time":"2019-09-24T19:49:47Z","timestamp":1569354587000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-59250-3_8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017]]},"ISBN":["9783319592497","9783319592503"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-59250-3_8","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2017]]}}}