{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T20:19:25Z","timestamp":1725567565415},"publisher-location":"Berlin, Heidelberg","reference-count":15,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642163661"},{"type":"electronic","value":"9783642163678"}],"license":[{"start":{"date-parts":[[2010,1,1]],"date-time":"2010-01-01T00:00:00Z","timestamp":1262304000000},"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":[[2010]]},"DOI":"10.1007\/978-3-642-16367-8_28","type":"book-chapter","created":{"date-parts":[[2010,10,7]],"date-time":"2010-10-07T11:25:55Z","timestamp":1286450755000},"page":"341-345","source":"Crossref","is-referenced-by-count":2,"title":["Dynamic Approximate Vertex Cover and Maximum Matching"],"prefix":"10.1007","author":[{"given":"Krzysztof","family":"Onak","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ronitt","family":"Rubinfeld","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"5","key":"28_CR1","doi-asserted-by":"publisher","first-page":"669","DOI":"10.1145\/265910.265914","volume":"44","author":"D. Eppstein","year":"1997","unstructured":"Eppstein, D., Galil, Z., Italiano, G.F., Nissenzweig, A.: Sparsification\u2014a technique for speeding up dynamic graph algorithms. J. ACM\u00a044(5), 669\u2013696 (1997)","journal-title":"J. ACM"},{"key":"28_CR2","volume-title":"Dynamic graph algorithms","author":"D. Eppstein","year":"1997","unstructured":"Eppstein, D., Galil, Z., Italiano, G.F.: Dynamic graph algorithms. CRC Press, Boca Raton (1997)"},{"issue":"4","key":"28_CR3","doi-asserted-by":"publisher","first-page":"502","DOI":"10.1145\/320211.320215","volume":"46","author":"M.R. Henzinger","year":"1999","unstructured":"Henzinger, M.R., King, V.: Randomized fully dynamic graph algorithms with polylogarithmic time per operation. J. ACM\u00a046(4), 502\u2013516 (1999)","journal-title":"J. ACM"},{"issue":"4","key":"28_CR4","doi-asserted-by":"publisher","first-page":"723","DOI":"10.1145\/502090.502095","volume":"48","author":"J. Holm","year":"2001","unstructured":"Holm, J., de Lichtenberg, K., Thorup, M.: Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity. J. ACM\u00a048(4), 723\u2013760 (2001)","journal-title":"J. ACM"},{"key":"28_CR5","doi-asserted-by":"crossref","unstructured":"Thorup, M.: Worst-case update times for fully-dynamic all-pairs shortest paths. In: STOC, pp. 112\u2013119 (2005)","DOI":"10.1145\/1060590.1060607"},{"issue":"3","key":"28_CR6","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1007\/PL00009223","volume":"22","author":"P.N. Klein","year":"1998","unstructured":"Klein, P.N., Subramanian, S.: A fully dynamic approximation scheme for shortest paths in planar graphs. Algorithmica\u00a022(3), 235\u2013249 (1998)","journal-title":"Algorithmica"},{"key":"28_CR7","doi-asserted-by":"crossref","unstructured":"Thorup, M.: Fully-dynamic min-cut. In: STOC, pp. 224\u2013230 (2001)","DOI":"10.1145\/380752.380804"},{"key":"28_CR8","unstructured":"Sankowski, P.: Faster dynamic matchings and vertex connectivity. In: SODA, pp. 118\u2013126 (2007)"},{"key":"28_CR9","doi-asserted-by":"crossref","unstructured":"Micali, S., Vazirani, V.V.: An $O(\\sqrt{|V|}\\cdot |E|)$ algorithm for finding maximum matching in general graphs. In: FOCS, pp. 17\u201327 (1980)","DOI":"10.1109\/SFCS.1980.12"},{"key":"28_CR10","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: van Leeuwen, J. (ed.) WG 1993. LNCS, vol.\u00a0790, pp. 99\u2013111. Springer, Heidelberg (1994)"},{"issue":"1-3","key":"28_CR11","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1016\/j.tcs.2007.04.040","volume":"381","author":"M. Parnas","year":"2007","unstructured":"Parnas, M., Ron, D.: Approximating the minimum vertex cover in sublinear time and a connection to distributed algorithms. Theor. Comput. Sci.\u00a0381(1-3), 183\u2013196 (2007)","journal-title":"Theor. Comput. Sci."},{"issue":"2-3","key":"28_CR12","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1016\/j.tcs.2005.09.013","volume":"348","author":"J. Feigenbaum","year":"2005","unstructured":"Feigenbaum, J., Kannan, S., McGregor, A., Suri, S., Zhang, J.: On graph problems in a semi-streaming model. Theor. Comput. Sci.\u00a0348(2-3), 207\u2013216 (2005)","journal-title":"Theor. Comput. Sci."},{"key":"28_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"170","DOI":"10.1007\/11538462_15","volume-title":"Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques","author":"A. McGregor","year":"2005","unstructured":"McGregor, A.: Finding graph matchings in data streams. In: Chekuri, C., Jansen, K., Rolim, J.D.P., Trevisan, L. (eds.) APPROX 2005 and RANDOM 2005. LNCS, vol.\u00a03624, pp. 170\u2013181. Springer, Heidelberg (2005)"},{"key":"28_CR14","unstructured":"Zelke, M.: Weighted matching in the semi-streaming model. In: STACS, pp. 669\u2013680 (2008)"},{"key":"28_CR15","doi-asserted-by":"crossref","unstructured":"Lotker, Z., Patt-Shamir, B., Ros\u00e9n, A.: Distributed approximate matching. In: PODC, pp. 167\u2013174 (2007)","DOI":"10.1145\/1281100.1281126"}],"container-title":["Lecture Notes in Computer Science","Property Testing"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-16367-8_28","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,5]],"date-time":"2019-06-05T05:10:50Z","timestamp":1559711450000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-16367-8_28"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642163661","9783642163678"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-16367-8_28","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}