{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,12]],"date-time":"2026-06-12T10:16:27Z","timestamp":1781259387505,"version":"3.54.1"},"publisher-location":"Berlin, Heidelberg","reference-count":12,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540578994","type":"print"},{"value":"9783540483854","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1994]]},"DOI":"10.1007\/3-540-57899-4_44","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T08:41:21Z","timestamp":1330245681000},"page":"99-111","source":"Crossref","is-referenced-by-count":15,"title":["Fully dynamic maintenance of vertex cover"],"prefix":"10.1007","author":[{"given":"Zoran","family":"Ivkovi\u0107","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Errol L.","family":"Lloyd","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2005,5,26]]},"reference":[{"key":"9_CR1","first-page":"27","volume":"25","author":"R. Bar-Yehuda","year":"1985","unstructured":"R. Bar-Yehuda and S. Even. (1985). A Local\u2014Ratio Theorem for Approximating the Weighted Vertex Cover Problem. Annals of Discrete Mathematics 25, pp. 27\u201346.","journal-title":"Annals of Discrete Mathematics"},{"issue":"1","key":"9_CR2","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1016\/0020-0190(83)90007-8","volume":"16","author":"K. L. Clarkson","year":"1983","unstructured":"K. L. Clarkson. (1983). A Modification of the Greedy Algorithm for Vertex Cover. Information Processing Letters\n16(1), pp. 23\u201325.","journal-title":"Information Processing Letters"},{"key":"9_CR3","doi-asserted-by":"crossref","unstructured":"D. Eppstein, Z. Galil, G. F. Italiano, and A. Nissenzweig. (1992). Sparsification \u2014 A Technique for Speeding up Dynamic Graph Algorithms. Proceedings of the 33rd IEEE Symposium on Foundations of Computer Science, pp. 60\u201369.","DOI":"10.1109\/SFCS.1992.267818"},{"issue":"4","key":"9_CR4","doi-asserted-by":"crossref","first-page":"781","DOI":"10.1137\/0214055","volume":"14","author":"G. Frederickson","year":"1985","unstructured":"G. Frederickson. (1985). Data Structures for On-Line Updating of Minimum Spanning Trees, with Applications. SIAM Journal on Computing\n14(4), pp. 781\u2013798.","journal-title":"SIAM Journal on Computing"},{"key":"9_CR5","unstructured":"Z. Galil, G. F. Italiano, and N. Sarnak. (1992). Fully Dynamic Planarity Testing. Proceedings of the 24th ACM Symposium on Theory of Computing, pp. 495\u2013506."},{"key":"9_CR6","volume-title":"Computers and Intractability: A Guide to the Theory of NP\u2014Completeness","author":"M. R. Garey","year":"1979","unstructured":"M. R. Garey and D. S. Johnson. (1979). Computers and Intractability: A Guide to the Theory of NP\u2014Completeness. Freeman, San Francisco."},{"key":"9_CR7","first-page":"134","volume-title":"Computers and Intractability: A Guide to the Theory of NP\u2014Completeness","author":"F. Gavril","year":"1974","unstructured":"F. Gavril. (1974). See [6,."},{"key":"9_CR8","doi-asserted-by":"crossref","unstructured":"Z. Ivkovi\u0107 and E. L. Lloyd. (1993). Fully Dynamic Algorithms for Bin Packing: Being (Mostly) Myopic Helps. Proceedings of the 1st European Symposium on Algorithms.","DOI":"10.1007\/3-540-57273-2_58"},{"key":"9_CR9","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Complexity of Computations","author":"R. M. Karp","year":"1972","unstructured":"R. M. Karp. (1972). Reducibility among Combinatorial Problems. In Complexity of Computations (R. E. Miller and J. W. Thatcher, Eds.), pp. 85\u2013103. Plenum, New York."},{"key":"9_CR10","unstructured":"P. N. Klein and S. Sairam. (1993). Fully Dynamic Approximation Schemes for Shortest Path Problems in Planar Graphs. Manuscript."},{"key":"9_CR11","doi-asserted-by":"crossref","first-page":"425","DOI":"10.1016\/0022-0000(91)90023-X","volume":"43","author":"C. H. Papadimitriou","year":"1991","unstructured":"C. H. Papadimitriou and M. Yannakakis. (1991). Optimization, Approximation, and Complexity Classes. Journal of Computer and System Sciences\n43, pp. 425\u2013440.","journal-title":"Journal of Computer and System Sciences"},{"issue":"5","key":"9_CR12","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1016\/0020-0190(82)90022-9","volume":"14","author":"C. Savage","year":"1982","unstructured":"C. Savage. (1982). Depth\u2014First Search and the Vertex Cover Problem. Information Processing Letters 14(5), pp. 233\u2013235.","journal-title":"Information Processing Letters"}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-57899-4_44.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T21:09:35Z","timestamp":1619557775000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-57899-4_44"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994]]},"ISBN":["9783540578994","9783540483854"],"references-count":12,"URL":"https:\/\/doi.org\/10.1007\/3-540-57899-4_44","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1994]]}}}