{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T15:12:10Z","timestamp":1787497930415,"version":"build-2736575974"},"publisher-location":"Berlin, Heidelberg","reference-count":11,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783662476710","type":"print"},{"value":"9783662476727","type":"electronic"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-662-47672-7_17","type":"book-chapter","created":{"date-parts":[[2015,6,19]],"date-time":"2015-06-19T06:07:39Z","timestamp":1434694059000},"page":"206-218","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["Design of Dynamic Algorithms via Primal-Dual Method"],"prefix":"10.1007","author":[{"given":"Sayan","family":"Bhattacharya","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Monika","family":"Henzinger","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Giuseppe F.","family":"Italiano","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2015,6,20]]},"reference":[{"key":"17_CR1","doi-asserted-by":"publisher","first-page":"198","DOI":"10.1016\/0196-6774(81)90020-1","volume":"2","author":"R Bar-Yehuda","year":"1981","unstructured":"Bar-Yehuda, R., Even, S.: A linear time approximation algorithm for the weighted vertex cover problem. Journal of Algorithms 2, 198\u2013203 (1981)","journal-title":"Journal of Algorithms"},{"key":"17_CR2","doi-asserted-by":"crossref","unstructured":"Baswana, S., Gupta, M., Sen, S.: Fully dynamic maximal matching in $${O}(\\log n)$$ update time. In: FOCS, pp. 383\u2013392 (2011)","DOI":"10.1109\/FOCS.2011.89"},{"key":"17_CR3","doi-asserted-by":"crossref","unstructured":"Bhattacharya, S., Henzinger, M., Italiano, G.F.: Deterministic fully dynamic data structures for vertex cover and matching. In: Procs. 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2015), pp. 785\u2013804 (2015)","DOI":"10.1137\/1.9781611973730.54"},{"issue":"2\u20133","key":"17_CR4","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1561\/0400000024","volume":"3","author":"N Buchbinder","year":"2009","unstructured":"Buchbinder, N., Naor, J.: The design of competitive online algorithms via a primal-dual approach. Foundations and Trends in Theoretical Computer Science 3(2\u20133), 93\u2013263 (2009)","journal-title":"Foundations and Trends in Theoretical Computer Science"},{"key":"17_CR5","doi-asserted-by":"crossref","unstructured":"Dantzig, G.B., Ford, L.R., Fulkerson, D.R.: A primal-dual algorithm for linear programs. In: Kuhn, H.W., Tucker, A.W. (eds.) Linear Inequalities and Related Systems, pp. 171\u2013181. Princeton University Press (1956)","DOI":"10.1515\/9781400881987-008"},{"key":"17_CR6","doi-asserted-by":"crossref","unstructured":"Eppstein, D., Galil, Z., Italiano, G.F.: Dynamic graph algorithms. In: Atallah, M.J., Blanton, M. (eds.) Algorithms and Theory of Computation Handbook, 2nd edn., vol. 1, pp. 9.1\u20139.28. CRC Press (2009)","DOI":"10.1201\/9781584888239-c9"},{"key":"17_CR7","doi-asserted-by":"crossref","unstructured":"Gupta, M., Peng, R.: Fully dynamic $$(1+\\epsilon )$$-approximate matchings. In: FOCS, pp. 548\u2013557 (2013)","DOI":"10.1109\/FOCS.2013.65"},{"key":"17_CR8","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1002\/nav.3800020109","volume":"2","author":"HW Kuhn","year":"1955","unstructured":"Kuhn, H.W.: The Hungarian method for the assignment problem. Naval Research Logistics Quarterly 2, 83\u201397 (1955)","journal-title":"Naval Research Logistics Quarterly"},{"key":"17_CR9","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":"17_CR10","doi-asserted-by":"crossref","unstructured":"Onak, K., Rubinfeld, R.: Maintaining a large matching and a small vertex cover. In: STOC, pp. 457\u2013464 (2010)","DOI":"10.1145\/1806689.1806753"},{"key":"17_CR11","volume-title":"Approximation Algorithms","author":"V Vazirani","year":"2001","unstructured":"Vazirani, V.: Approximation Algorithms. Springer-Verlag, NY (2001)"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages, and Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-47672-7_17","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,20]],"date-time":"2023-02-20T21:12:37Z","timestamp":1676927557000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-662-47672-7_17"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783662476710","9783662476727"],"references-count":11,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-47672-7_17","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"20 June 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}