{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,19]],"date-time":"2025-02-19T21:40:31Z","timestamp":1740001231455,"version":"3.37.3"},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540633976"},{"type":"electronic","value":"9783540695363"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1997]]},"DOI":"10.1007\/3-540-63397-9_25","type":"book-chapter","created":{"date-parts":[[2010,4,5]],"date-time":"2010-04-05T19:22:48Z","timestamp":1270495368000},"page":"326-340","source":"Crossref","is-referenced-by-count":1,"title":["Quasi-fully dynamic algorithms for two-connectivity, cycle equivalence and related problems"],"prefix":"10.1007","author":[{"given":"Madhukar R.","family":"Korupolu","sequence":"first","affiliation":[]},{"given":"Vijaya","family":"Ramachandran","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,7,30]]},"reference":[{"key":"25_CR1","unstructured":"David Alberts, Giuseppe Cattaneo, and Giuseppe F. Italiano. An empirical study of dynamic graph algorithms. In Proceedings of the Seventh Annual ACM SIAM Symp. on Discrete Algorithms, pages 192\u2013201, 1996."},{"issue":"4","key":"25_CR2","doi-asserted-by":"crossref","first-page":"450","DOI":"10.1137\/0403039","volume":"3","author":"D. A. Aldous","year":"1990","unstructured":"David A. Aldous. The random walk construction of uniform spanning trees and uniform labelled trees. Siam J. Disc. Math., 3(4):450\u2013465, November 1990.","journal-title":"Siam J. Disc. Math."},{"key":"25_CR3","unstructured":"D. Eppstein, Z. Galil, and G. Italiano. Improved sparsification. Technical Report 93\u201320, University of California at Irvine, Dept of Information and Computer Science, 1993."},{"key":"25_CR4","unstructured":"J. Feigenbaum and Sampath Kannan. Handbook of Discrete and Combinatorial Mathematics, chapter Dynamic Graph Algorithms, pages 583\u2013591. 1995."},{"key":"25_CR5","doi-asserted-by":"crossref","unstructured":"G.N. Frederickson. Ambivalent data structures for dynamic 2-edge connectivity and k smallest spanning trees. In Proceedings of 32nd Symp. on Foundations of Computer Science, pages 632\u2013641, 1991.","DOI":"10.1109\/SFCS.1991.185429"},{"key":"25_CR6","unstructured":"R. Gupta and M.L. Soffa. Region scheduling. In Proc. 2nd International Conference on Supercomputing, pages 141\u2013148, 1987."},{"key":"25_CR7","doi-asserted-by":"crossref","unstructured":"M. Rauch Henzinger. Fully dynamic biconnectivity in graphs. In Proceedings of 33rd Symp. on Foundations of Computer Science, pages 50\u201359, 1992.","DOI":"10.1109\/SFCS.1992.267819"},{"key":"25_CR8","doi-asserted-by":"crossref","unstructured":"M. Rauch Henzinger. Fully dynamic cycle equivalence in graphs. In Proceedings of 35th Symposium on Foundations of Computer Science, pages 744\u2013755, 1994.","DOI":"10.1109\/SFCS.1994.365718"},{"key":"25_CR9","doi-asserted-by":"crossref","unstructured":"M. Rauch Henzinger and V. King. Randomized dynamic algorithms with polylogarithmic time per operation. In Proceedings of 27th Annual Symp. on Theory of Computing, pages 519\u2013527, 1995.","DOI":"10.1145\/225058.225269"},{"key":"25_CR10","doi-asserted-by":"crossref","unstructured":"M. Rauch Henzinger and J. A. La Poutre. Certificates and fast algorithms for biconnectivity in fully-dynamic graphs. In Proceedings of Third Annual European Symposium on Algorithms (ESA), pages 171\u2013184, 1995.","DOI":"10.1007\/3-540-60313-1_142"},{"key":"25_CR11","unstructured":"Monika Henzinger and Valerie King. Personal communication, July\u2013August 1996."},{"key":"25_CR12","doi-asserted-by":"crossref","unstructured":"M.R Henzinger and Valerie King. Fully dynamic biconnectivity and transitive closure. In Proceedings 36th Symp. on Foundations of Computer Science, pages 664\u2013672, 1995.","DOI":"10.1109\/SFCS.1995.492668"},{"key":"25_CR13","doi-asserted-by":"crossref","unstructured":"Richard Johnson, David Pearson, and Keshav Pingali. Finding regions fast: Single entry single exit and control regions in linear time. In Proceedings of ACM SIGPLAN '94 Conference on Programming Language Design and Implementation, pages 171\u2013185, 1994.","DOI":"10.1145\/178243.178258"},{"key":"25_CR14","unstructured":"Valerie King. Personal communication, July 1996."},{"key":"25_CR15","doi-asserted-by":"crossref","unstructured":"Madhukar R. Korupolu and Vijaya Ramachandran. Quasi-fully dynamic algorithms for two-connectivity, cycle equivalence and related problems. Technical report TR97-14, Univ. of Texas at Austin, Dept. of Computer Sciences, 1997.","DOI":"10.1007\/3-540-63397-9_25"},{"key":"25_CR16","unstructured":"Madhukar R. Korupolu. Randomized fully dynamic two edge connectivity: A variant of the Henzinger-King sketch. Manuscript, Univ of Texas at Austin, May 1997."},{"key":"25_CR17","unstructured":"J.A. La Poutre. Maintenance of 2-and 3-connected components of graphs, part ii: 2-and 3-edge connected components and 2-vertex connected components. Technical Report RUU-CS-90-27, Utrecht University, 1990."},{"key":"25_CR18","unstructured":"J.A. La Poutre and J. Westbrook. Dynamic two-connectivity with backtracking. In Proceedings of 4th Symp. on Discrete Algorithms, pages 204\u2013212, 1994."},{"issue":"1","key":"25_CR19","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1007\/BF02579206","volume":"7","author":"K. Mulmuley","year":"1987","unstructured":"Ketan Mulmuley, U.V. Vazirani, and V.V. Vazirani. Matching is as easy as matrix inversion. Combinatorica, 7(1):105\u2013113, 1987.","journal-title":"Combinatorica"},{"key":"25_CR20","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":"25_CR21","doi-asserted-by":"crossref","unstructured":"R.E Tarjan and Valdes Jacobo. Prime subprogram parsing of a program. In Conference record of the Seventh Annual ACM Symp. on Principles of Programming Languages, pages 28\u201330, 1980.","DOI":"10.1145\/567446.567456"},{"key":"25_CR22","unstructured":"J. Westbrook. Algorithms and Data Structures for Dynamic Graph Problems. PhD thesis, Dept of Computer Science, Princeton University, Princeton, NJ, 1989."},{"key":"25_CR23","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1137\/0218001","volume":"18","author":"J. Westbrook","year":"1989","unstructured":"J. Westbrook and R.E. Tarjan. Amortized analysis of algorithms for set union with backtracking. SIAM Jl. Computing, 18:1\u201311, 1989.","journal-title":"SIAM Jl. Computing"},{"key":"25_CR24","doi-asserted-by":"crossref","unstructured":"J. Westbrook and R.E. Tarjan. Maintaining bridge connected and biconnected components online. Algorithmica, pages 433\u2013464, 1992.","DOI":"10.1007\/BF01758773"}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2014 ESA '97"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-63397-9_25","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,19]],"date-time":"2025-02-19T21:15:21Z","timestamp":1739999721000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-63397-9_25"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997]]},"ISBN":["9783540633976","9783540695363"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/3-540-63397-9_25","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1997]]}}}