{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T22:56:10Z","timestamp":1725663370351},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540542339"},{"type":"electronic","value":"9783540475163"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1991]]},"DOI":"10.1007\/3-540-54233-7_146","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T22:37:54Z","timestamp":1330209474000},"page":"339-350","source":"Crossref","is-referenced-by-count":13,"title":["Maintaining biconnected components of dynamic planar graphs"],"prefix":"10.1007","author":[{"given":"Zvi","family":"Galil","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Giuseppe F.","family":"Italiano","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,8]]},"reference":[{"key":"26_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":"26_CR2","doi-asserted-by":"crossref","unstructured":"G. Ausiello, G. F. Italiano, A. Marchetti-Spaccamela, U. Nanni, \u201cIncremental algorithms for minimal length paths\u201d, J. Algorithms, to appear.","DOI":"10.1016\/0196-6774(91)90036-X"},{"key":"26_CR3","doi-asserted-by":"crossref","unstructured":"G. Di Battista, and R. Tamassia, \u201cIncremental planarity testing\u201d, Proc. 30th Annual Symp. on Foundations of Computer Science, 1989, 436\u2013441.","DOI":"10.1109\/SFCS.1989.63515"},{"key":"26_CR4","first-page":"598","volume-title":"Proc. 17th Int. Colloquium on Automata, Languages and Programming, Lecture Notes in Computer Science","author":"G. Battista Di","year":"1990","unstructured":"G. Di Battista, and R. Tamassia, \u201cOn-line graph algorithms with SPQR-trees\u201d, Proc. 17th Int. Colloquium on Automata, Languages and Programming, Lecture Notes in Computer Science 443, Springer-Verlag, Berlin, 1990, 598\u2013611."},{"key":"26_CR5","unstructured":"D. Eppstein, G. F. Italiano, R. Tamassia, R. E. Tarjan, J. Westbrook, and M. Yung, \u201cMaintenance of a minimum spanning forest in a dynamic planar graph\u201d, Proc. First Annual ACM-SIAM Symp. on Discrete Algorithms, 1990, 1\u201311."},{"key":"26_CR6","first-page":"371","volume":"49","author":"S. Even","year":"1985","unstructured":"S. Even, and H. Gazit, \u201cUpdating distances in dynamic graphs\u201d, Methods of Operations Research 49 (1985), 371\u2013387.","journal-title":"Methods of Operations Research"},{"key":"26_CR7","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, \u201cAn on-line edge deletion problem\u201d, J. Assoc. Comput. Mach. 28 (1981), 1\u20134.","journal-title":"J. Assoc. Comput. Mach."},{"key":"26_CR8","doi-asserted-by":"crossref","first-page":"781","DOI":"10.1137\/0214055","volume":"14","author":"G. N. Frederickson","year":"1985","unstructured":"G. N. Frederickson, \u201cData structures for on-line updating of minimum spanning trees\u201d, SIAM J. Comput. 14 (1985), 781\u2013798.","journal-title":"SIAM J. Comput."},{"key":"26_CR9","doi-asserted-by":"crossref","unstructured":"Z. Galil, and G. F. Italiano, \u201cFully dynamic algorithms for edge connectivity problems\u201d, Proc. 23rd Annual ACM Symp. on Theory of Computing, 1991.","DOI":"10.1145\/103418.103454"},{"key":"26_CR10","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":"26_CR11","doi-asserted-by":"crossref","first-page":"273","DOI":"10.1016\/0304-3975(86)90098-8","volume":"48","author":"G. F. Italiano","year":"1986","unstructured":"G. F. Italiano, \u201cAmortized efficiency of a path retrieval data structure\u201d, Theoret. Comput. Sci. 48 (1986), 273\u2013281.","journal-title":"Theoret. Comput. Sci."},{"key":"26_CR12","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1016\/0020-0190(88)90136-6","volume":"28","author":"G. F. Italiano","year":"1988","unstructured":"G. F. Italiano, \u201cFinding paths and deleting edges in directed acyclic graphs\u201d, Inform. Process. Lett. 28 (1988), 5\u201311.","journal-title":"Inform. Process. Lett."},{"key":"26_CR13","doi-asserted-by":"crossref","first-page":"106","DOI":"10.1007\/3-540-19422-3_9","volume-title":"Proc. Workshop on Graph-Theoretic Concepts in Computer Science, Lecture Notes in Computer Science","author":"J. A. Poutr\u00e9 La","year":"1988","unstructured":"J. A. La Poutr\u00e9, and J. van Leeuwen, \u201cMaintenance of transitive closure and transitive reduction of graphs\u201d, Proc. Workshop on Graph-Theoretic Concepts in Computer Science, Lecture Notes in Computer Science, vol. 314, Springer-Verlag, Berlin, 1988, 106\u2013120."},{"key":"26_CR14","doi-asserted-by":"crossref","unstructured":"F. P. Preparata, and R. Tamassia, \u201cFully dynamic techniques for point location and transitive closure in planar structures\u201d, Proc. 29th Annual Symp. on Foundations of Computer Science, 1988, 558\u2013567.","DOI":"10.1109\/SFCS.1988.21972"},{"key":"26_CR15","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, \u201cA topological approach to dynamic graph connectivity\u201d, Inform. Process. Lett. 25 (1987), 65\u201370.","journal-title":"Inform. Process. Lett."},{"key":"26_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"279","DOI":"10.1007\/BFb0024016","volume-title":"Proc. 2nd Annual Symp. on Theoretical Aspects of Computer Science","author":"H. Rohnert","year":"1985","unstructured":"H. Rohnert, \u201cA dynamization of the all pairs least cost path problem\u201d, Proc. 2nd Annual Symp. on Theoretical Aspects of Computer Science, Lecture Notes in Computer Science, vol. 182, Springer-Verlag, Berlin, 1985, 279\u2013286."},{"key":"26_CR17","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, \u201cA data structure for dynamic trees\u201d, J. Comput. System Sci. 24 (1983), 362\u2013381.","journal-title":"J. Comput. System Sci."},{"key":"26_CR18","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1137\/0201010","volume":"1","author":"R. E. Tarjan","year":"1972","unstructured":"R. E. Tarjan, \u201cDepth first search and linear graph algorithms\u201d, SIAM J. Comput. 1 (1972), 149\u2013160.","journal-title":"SIAM J. Comput."},{"key":"26_CR19","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, \u201cWorst case analysis of set union algorithms\u201d, J. Assoc. Comput. Mach. 31 (1984), 245\u2013281.","journal-title":"J. Assoc. Comput. Mach."},{"key":"26_CR20","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, \u201cAn efficient parallel biconnectivity algorithm\u201d, SIAM J. Comput. 14 (1985), 862\u2013864.","journal-title":"SIAM J. Comput."},{"key":"26_CR21","doi-asserted-by":"crossref","unstructured":"J. Westbrook, and R. E. Tarjan, \u201cMaintaining bridge-connected and biconnected components on-line\u201d, Tech. Rep. CS-TR-228-89, Department of Computer Science, Princeton University, August 1989. To appear in Algorithmica.","DOI":"10.21236\/ADA215107"},{"key":"26_CR22","unstructured":"D. M. Yellin, \u201cA dynamic transitive closure algorithm\u201d, Research Report, IBM Research Division, T. J. Watson Research Center, 1988."}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-54233-7_146.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T20:53:14Z","timestamp":1605646394000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-54233-7_146"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1991]]},"ISBN":["9783540542339","9783540475163"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/3-540-54233-7_146","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1991]]}}}