{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,19]],"date-time":"2026-05-19T07:15:22Z","timestamp":1779174922722,"version":"3.51.4"},"reference-count":18,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[1995,6,1]],"date-time":"1995-06-01T00:00:00Z","timestamp":801964800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[1995,6]]},"DOI":"10.1007\/bf01189067","type":"journal-article","created":{"date-parts":[[2005,2,17]],"date-time":"2005-02-17T22:39:28Z","timestamp":1108679968000},"page":"503-538","source":"Crossref","is-referenced-by-count":15,"title":["Fully dynamic biconnectivity in graphs"],"prefix":"10.1007","volume":"13","author":[{"given":"M. R.","family":"Henzinger","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"CR1","volume-title":"The Design and Analysis of Computer Algorithms","author":"A. V. Aho","year":"1974","unstructured":"A. V. Aho, J. E. Hopcroft, and J. D. Ullman,The Design and Analysis of Computer Algorithms, Addison-Wesley, Reading, MA, 1974."},{"key":"CR2","unstructured":"B. Alpern, R. Hoover, B. Rosen, P. Sweeney, and F. K. Zadeck, Incremental Evaluation of Computational Circuits,Proc. 1st Annual ACM-SIAM Symp. on Discrete Algorithms, 1990, pp. 32?42."},{"key":"CR3","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1016\/0743-1066(91)90006-B","volume":"10","author":"G. Ausiello","year":"1991","unstructured":"G. Ausiello and G. F. Italiano, On-Line Algorithms for Polynomially Solvable Satisfiability Problems,J. Logic Programming,10 (1991), 69?90.","journal-title":"J. Logic Programming"},{"key":"CR4","doi-asserted-by":"crossref","unstructured":"M. D. Carrol and B. G. Ryder, Incremental Data Flow Analysis via Dominator and Attribute Updates,Proc. 15th Annual ACM SIGACT-SIGPLAN Symp. on Principles of Programming Languages, 1988, pp. 274?284.","DOI":"10.1145\/73560.73584"},{"key":"CR5","unstructured":"D. Eppstein, G. F. Italiano, R. Tamassia, R. E. Tarjan, J. Westbrook, and M. Yung, Maintenance of a Minimum Spanning Forest in a Dynamic Planar Graph,Proc. 1st Annual Symp. on Discrete Algorithms 1990, pp. 1?11."},{"key":"CR6","doi-asserted-by":"crossref","unstructured":"D. Eppstein, Z. Galil, G. F. Italiano, and A. Nissenzweig, Sparsification?A Technique for Speeding Up Dynamic Graph Algorithms,Proc. 32nd Annual Symp. on Foundations of Computer Science, 1992.","DOI":"10.1109\/SFCS.1992.267818"},{"key":"CR7","volume-title":"Technical Report 92-20","author":"D. Eppstein","year":"1993","unstructured":"D. Eppstein, Z. Galil, and G. F. Italiano, Improved Sparsification, Technical Report 92-20, Department of Information and Computer Science, University of California, Irvine, CA, 1993."},{"key":"CR8","doi-asserted-by":"crossref","first-page":"781","DOI":"10.1137\/0214055","volume":"14","author":"G. N. Frederickson","year":"1985","unstructured":"G. N. Frederickson, Data Structures for On-Line Updating of Minimum Spanning Trees,SIAM J. Comput.,14 (1985), 781?798.","journal-title":"SIAM J. Comput."},{"key":"CR9","doi-asserted-by":"crossref","unstructured":"G. N. Frederickson, Ambivalent Data Structures for Dynamic 2-Edge-Connectivity andk Smallest Spanning Trees,Proc. 32nd Annual IEEE Symps. on Foundation of Computer Science, 1991, pp. 632?641.","DOI":"10.1109\/SFCS.1991.185429"},{"key":"CR10","first-page":"339","volume-title":"Lecture Notes in Computer Science","author":"Z. Galil","year":"1991","unstructured":"Z. Galil and G. F. Italiano, Maintaining Biconnected Components of Dynamic Planar Graphs,Proc. 18th ICALP, Lecture Notes in Computer Science, Springer-Verlag, Berlin, 1991, pp. 339?350."},{"key":"CR11","doi-asserted-by":"crossref","DOI":"10.21236\/AD0705364","volume-title":"Graph Theory","author":"F. Harary","year":"1969","unstructured":"F. Harary,Graph Theory, Addison-Wesley, Reading, MA, 1969."},{"key":"CR12","unstructured":"M. R. Henzinger and V. King, Randomized Dynamic Algorithms with Polylogarithmic Time per Operation, in preparation."},{"key":"CR13","first-page":"233","volume-title":"Lecture Notes in Computer Science, Vol. 621","author":"J. Hershberger","year":"1992","unstructured":"J. Hershberger, M. Rauch and S. Suri, Fully Dynamic 2-Edge-Connectivity in Planar Graphs,Proc. 3rd Scandinavian Workshop on Algorithm Theory, Lecture Notes in Computer Science, Vol. 621, Springer-Verlag, Berlin, 1992, pp. 233?244."},{"key":"CR14","unstructured":"G. Italiano, Private communication."},{"key":"CR15","doi-asserted-by":"crossref","first-page":"362","DOI":"10.1016\/0022-0000(83)90006-5","volume":"24","author":"D. D. Sleator","year":"1983","unstructured":"D. D. Sleator and R. E. Tarjan, A Data Structure for Dynamic Trees,J. Comput. System Sci.,24 (1983), 362?381.","journal-title":"J. Comput. System Sci."},{"key":"CR16","doi-asserted-by":"crossref","first-page":"146","DOI":"10.1137\/0201010","volume":"1","author":"R. E. Tarjan","year":"1972","unstructured":"R. E. Tarjan, Depth First Search and Linear Graph Algorithms,SIAM J. Comput.,1 (1972), 146?160.","journal-title":"SIAM J. Comput."},{"key":"CR17","doi-asserted-by":"crossref","first-page":"433","DOI":"10.1007\/BF01758773","volume":"7","author":"R. E. Tarjan","year":"1992","unstructured":"R. E. Tarjan and J. Westbrook, Maintaining Bridge-Connected and Biconnected Components On-Line,Algorithmica,7 (1992), 433?464.","journal-title":"Algorithmica"},{"key":"CR18","doi-asserted-by":"crossref","unstructured":"M. Yannakakis, Graph Theoretic Methods in Database Theory,Proc. ACM Conf. on Principles of Database Systems, 1990, pp. 230?242.","DOI":"10.1145\/298514.298576"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01189067.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01189067\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01189067","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,12,23]],"date-time":"2024-12-23T11:43:10Z","timestamp":1734954190000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01189067"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995,6]]},"references-count":18,"journal-issue":{"issue":"6","published-print":{"date-parts":[[1995,6]]}},"alternative-id":["BF01189067"],"URL":"https:\/\/doi.org\/10.1007\/bf01189067","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[1995,6]]}}}