{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T15:48:59Z","timestamp":1787500139399,"version":"build-2736575974"},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"1-6","license":[{"start":{"date-parts":[[1992,6,1]],"date-time":"1992-06-01T00:00:00Z","timestamp":707356800000},"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":[[1992,6]]},"DOI":"10.1007\/bf01758773","type":"journal-article","created":{"date-parts":[[2005,6,15]],"date-time":"2005-06-15T06:49:08Z","timestamp":1118818148000},"page":"433-464","source":"Crossref","is-referenced-by-count":83,"title":["Maintaining bridge-connected and biconnected components on-line"],"prefix":"10.1007","volume":"7","author":[{"given":"Jeffery","family":"Westbrook","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Robert E.","family":"Tarjan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"BF01758773_CR1","doi-asserted-by":"crossref","first-page":"1258","DOI":"10.1109\/TC.1987.1676869","volume":"36","author":"B. Awerbuch","year":"1987","unstructured":"B. Awerbuch and Y. Shiloach. New connectivity and msf algorithms for shuffle-exchange network and PRAM.IEEE Trans. Comput.,36:1258\u20131263, 1987.","journal-title":"IEEE Trans. Comput."},{"key":"BF01758773_CR2","doi-asserted-by":"crossref","unstructured":"G. D. Battista and R. Tamassia. Incremental planarity testing.Proc. 30th IEEE Symposium on Foundations of Computer Science, pages 436\u2013441, 1989.","DOI":"10.1109\/SFCS.1989.63515"},{"key":"BF01758773_CR3","first-page":"598","volume-title":"Lecture Notes in Computer Science, vol. 443","author":"G. D. Battista","year":"1990","unstructured":"G. D. Battista and R. Tamassia. On-line graph algorithms with spqr-trees.Proc. 17th Internat. Conf. on Automata, Languages, and Programming (ICALP 1990). Lecture Notes in Computer Science, vol. 443, pages 598\u2013611. Springer-Verlag, Berlin, 1990."},{"key":"BF01758773_CR4","doi-asserted-by":"crossref","first-page":"1021","DOI":"10.1137\/0215072","volume":"15","author":"N. Blum","year":"1986","unstructured":"N. Blum. On the single-operation worst-case time complexity of the disjoint set union problem.SIAM J. Comput., 15:1021\u20131024, 1986.","journal-title":"SIAM J. Comput."},{"key":"BF01758773_CR5","unstructured":"G. A. Cheston. Incremental Algorithms in Graph Theory. Ph.D. thesis, Dept. of Computer Science, University of Toronto, 1976. Technical Report No. 91."},{"key":"BF01758773_CR6","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/322234.322235","volume":"28","author":"S. Even","year":"1981","unstructured":"S. Even and Y. Shiloach. An on-line edge deletion problem.J. Assoc. Comput. Mach.,28:1\u20134, 1981.","journal-title":"J. Assoc. Comput. Mach."},{"key":"BF01758773_CR7","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, with applications.SIAM J. Comput.,14:781\u2013798, 1985.","journal-title":"SIAM J. Comput."},{"key":"BF01758773_CR8","doi-asserted-by":"crossref","unstructured":"M. L. Fredman and M. E. Saks. The cell probe complexity of dynamic data structures.Proc. 21st ACM Symposium on Theory of Computing, pages 345\u2013354, Seattle, WA, May 1989.","DOI":"10.1145\/73007.73040"},{"key":"BF01758773_CR9","doi-asserted-by":"crossref","first-page":"372","DOI":"10.1145\/362248.362272","volume":"16","author":"J. Hopcroft","year":"1973","unstructured":"J. Hopcroft and R. E. Tarjan. Algorithm 447: Efficient algorithms for graph manipulation.Comm. ACM,16:372\u2013378, 1973.","journal-title":"Comm. ACM"},{"key":"BF01758773_CR10","first-page":"869","volume-title":"Handbook of Theoretical Computer Science","author":"R. Karp","year":"1990","unstructured":"R. Karp and V. Ramachandran. Parallel Algorithms for Shared Memory Machines.Handbook of Theoretical Computer Science, Elsevier, Amsterdam, 1990, pages 869\u2013942."},{"key":"BF01758773_CR11","doi-asserted-by":"crossref","unstructured":"J. A. La Poutr\u00e9. Lower bounds for the union-find and split-find problem on pointer machines.Proc. 22nd ACM Symposium on Theory of Computing, pages 34\u201344, 1990.","DOI":"10.1145\/100216.100221"},{"key":"BF01758773_CR12","unstructured":"J. A. La Poutr\u00e9, J. van Leeuwen, and M. H. Overmars. Maintenance of 2- and 3-Connected Components of Graphs, Part I: 2- and 3-Edge-Connected Components. Technical Report RUU-CS-90-26, Utrecht University, 1990."},{"key":"BF01758773_CR13","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1016\/0020-0190(87)90095-0","volume":"25","author":"J. H. Reif","year":"1987","unstructured":"J. H. Reif. A topological approach to dynamic graph connectivity.Inform. Process. Lett.,25:65\u201370, 1987.","journal-title":"Inform. Process. Lett."},{"key":"BF01758773_CR14","doi-asserted-by":"crossref","first-page":"362","DOI":"10.1016\/0022-0000(83)90006-5","volume":"26","author":"D. D. Sleator","year":"1983","unstructured":"D. D. Sleator and R. E. Tarjan. A data structure for dynamic trees.J. Comput. System Sci.,26:362\u2013391, 1983.","journal-title":"J. Comput. System Sci."},{"key":"BF01758773_CR15","doi-asserted-by":"crossref","first-page":"652","DOI":"10.1145\/3828.3835","volume":"32","author":"D. D. Sleator","year":"1985","unstructured":"D. D. Sleator and R. E. Tarjan. Self-adjusting binary search trees.J. Assoc. Comput. Mach.,32:652\u2013686, 1985.","journal-title":"J. Assoc. Comput. Mach."},{"key":"BF01758773_CR16","first-page":"576","volume-title":"Lecture Notes in Computer Science, vol. 317","author":"R. Tamassia","year":"1988","unstructured":"R. Tamassia. A dynamic data structure for planar graph embedding.Proc. 15th Internat. Conf. on Automata, Languages, and Programming (ICALP1988). Lecture Notes in Computer Science, vol. 317, pages 576\u2013590. Springer-Verlag, Berlin, 1988."},{"key":"BF01758773_CR17","doi-asserted-by":"crossref","unstructured":"R. Tamassia. Dynamic Data Structures for Two-Dimensional Searching. Ph.D. thesis, Coordinated Science Laboratory, University of Illinois at Urbana-Champagne, 1988. Technical Report ACT-100.","DOI":"10.21236\/ADA201173"},{"key":"BF01758773_CR18","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:146\u2013160, 1972.","journal-title":"SIAM J. Comput."},{"key":"BF01758773_CR19","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1145\/321879.321884","volume":"22","author":"R. E. Tarjan","year":"1975","unstructured":"R. E. Tarjan. Efficiency of a good but not linear set union algorithm.J. Assoc. Comput. Mach.,22:215\u2013225, 1975.","journal-title":"J. Assoc. Comput. Mach."},{"key":"BF01758773_CR20","doi-asserted-by":"crossref","first-page":"110","DOI":"10.1016\/0022-0000(79)90042-4","volume":"18","author":"R. E. Tarjan","year":"1979","unstructured":"R. E. Tarjan. A class of algorithms which require nonlinear time to maintain disjoint sets.J. Comput. System Sci.,18:110\u2013127, 1979.","journal-title":"J. Comput. System Sci."},{"key":"BF01758773_CR21","doi-asserted-by":"crossref","DOI":"10.1137\/1.9781611970265","volume-title":"Data Structures and Network Algorithms","author":"R. E. Tarjan","year":"1983","unstructured":"R. E. Tarjan.Data Structures and Network Algorithms. Society for Industrial and Applied Mathematics, Philadelphia, PA, 1983."},{"key":"BF01758773_CR22","doi-asserted-by":"crossref","first-page":"306","DOI":"10.1137\/0606031","volume":"6","author":"R. E. Tarjan","year":"1985","unstructured":"R. E. Tarjan. Amortized computational complexity.SIAM J. Algebraic Discrete Methods,6:306\u2013318, 1985.","journal-title":"SIAM J. Algebraic Discrete Methods"},{"key":"BF01758773_CR23","doi-asserted-by":"crossref","first-page":"245","DOI":"10.1145\/62.2160","volume":"31","author":"R. E. Tarjan","year":"1984","unstructured":"R. E. Tarjan and J. van Leeuwen. Worst-case analysis of set union algorithms.J. Assoc. Comput. Mach.,31:245\u2013281, 1984.","journal-title":"J. Assoc. Comput. Mach."},{"key":"BF01758773_CR24","doi-asserted-by":"crossref","first-page":"862","DOI":"10.1137\/0214061","volume":"14","author":"R. E. Tarjan","year":"1985","unstructured":"R. E. Tarjan and U. Vishkin. An efficient parallel biconnectivity algorithm.SIAM J. Comput.,14:862\u2013874, 1985.","journal-title":"SIAM J. Comput."},{"key":"BF01758773_CR25","series-title":"Technical Report CS-TR-228-89","doi-asserted-by":"crossref","DOI":"10.21236\/ADA215107","volume-title":"Maintaining Bridge-Connected and Biconnected Components On-Line","author":"J. Westbrook","year":"1989","unstructured":"J. Westbrook and R. E. Tarjan. Maintaining Bridge-Connected and Biconnected Components On-Line. Technical Report CS-TR-228-89, Dept. of Computer Science, Princeton University, Princeton, NJ, 1989."},{"key":"BF01758773_CR26","doi-asserted-by":"crossref","first-page":"615","DOI":"10.1145\/322261.322274","volume":"28","author":"A. C. Yao","year":"1981","unstructured":"A. C. Yao. Should tables be sorted?J. Assoc. Comput. Mach.,28:615\u2013628, 1981.","journal-title":"J. Assoc. Comput. Mach."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01758773.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01758773\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01758773","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,7]],"date-time":"2020-04-07T14:57:18Z","timestamp":1586271438000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01758773"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1992,6]]},"references-count":26,"journal-issue":{"issue":"1-6","published-print":{"date-parts":[[1992,6]]}},"alternative-id":["BF01758773"],"URL":"https:\/\/doi.org\/10.1007\/bf01758773","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[1992,6]]}}}