{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:07:38Z","timestamp":1725664058046},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540578994"},{"type":"electronic","value":"9783540483854"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1994]]},"DOI":"10.1007\/3-540-57899-4_43","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T13:41:16Z","timestamp":1330263676000},"page":"87-98","source":"Crossref","is-referenced-by-count":1,"title":["Average case analysis of fully dynamic connectivity for directed graphs"],"prefix":"10.1007","author":[{"given":"Paola","family":"Alimonti","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stefano","family":"Leonardi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alberto","family":"Marchetti-Spacccamela","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xavier","family":"Messeguer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,5,26]]},"reference":[{"key":"8_CR1","doi-asserted-by":"crossref","first-page":"615","DOI":"10.1016\/0196-6774(91)90036-X","volume":"12","author":"G. Ausiello","year":"1991","unstructured":"G. Ausiello, G. F. Italiano, A. Marchetti-Spaccamela, U. Nanni, \u201cIncremental algorithms for minimal length paths\u201d, J. of Algorithms, 12 (1991), 615\u2013638.","journal-title":"J. of Algorithms"},{"key":"8_CR2","doi-asserted-by":"crossref","unstructured":"A. Blum, \u201cSome tools for approximate 3-coloring\u201d, Proceedings of the 31st IEEE Symposium on Foundations of Computer Science, 1990.","DOI":"10.1109\/FSCS.1990.89576"},{"key":"8_CR3","unstructured":"B. Bollobas, \u201cRandom graphs\u201d, Academic Press, 1985."},{"key":"8_CR4","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.","DOI":"10.1109\/SFCS.1989.63515"},{"key":"8_CR5","doi-asserted-by":"crossref","unstructured":"G. Di Battista and R.Tamassia, \u201cOn-line graph algorithms with SPQR-trees\u201d, Proc. 17th Int. Coll. on Automata, Languages and Programming, Lect. Not. in Comp. Sci., Springer-Verlag, 1990.","DOI":"10.1007\/BFb0032061"},{"key":"8_CR6","doi-asserted-by":"crossref","unstructured":"D. Eppstein, Z.Galil, G. F. Italiano, A.Nissenzweig, \u201cSparsification \u2014 a technique for speeding up dynamic graph algorithms\u201d, Proc. 33rd Symp. on Found. of Computer Sci. 1992.","DOI":"10.1109\/SFCS.1992.267818"},{"key":"8_CR7","unstructured":"D. Eppstein, G. F. Italiano, R. Tamassia, R. E. Tarjan, J. Westbrook, M. Young, \u201cMaintenance of a minimum spanning forest in a dynamic planar graph\u201d, Proc. 1st ACM-SIAM Symp. on Discrete Algorithms, S.Francisco, 1990."},{"key":"8_CR8","doi-asserted-by":"crossref","unstructured":"P. Erd\u00f6s, A. R\u00e8nyi, \u201cOn random graphs I\u201d, Publ. Math. Debrecen, 6, 290\u2013297.","DOI":"10.5486\/PMD.1959.6.3-4.12"},{"key":"8_CR9","unstructured":"S. Even and H. Gazit, \u201cUpdating distances in dynamic graphs\u201d, Methods of Operations Research, 49, 1985."},{"key":"8_CR10","doi-asserted-by":"crossref","unstructured":"Z. Galil, G.F. Italiano, \u201cFully dynamic algorithms for edge-connectivity problems\u201d, Proc. 23rd ACM Symp. on Theory of Comp., (1991) 317\u2013327.","DOI":"10.1145\/103418.103454"},{"issue":"1","key":"8_CR11","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1145\/122413.122416","volume":"22","author":"Z. Galil","year":"1991","unstructured":"Z. Galil, G.F. Italiano, \u201cReducing edge connectivity to vertex connectivity\u201d, SIGACT News, 22 (1) (1991) 57\u201361.","journal-title":"SIGACT News"},{"key":"8_CR12","unstructured":"R.M. Karp, \u201cThe transitive closure of a random digraph\u201d, Technical Report-89-047, International Computer Science Institute (ICSI), August 1989."},{"key":"8_CR13","doi-asserted-by":"crossref","unstructured":"R.M. Karp, R.E. Tarjan, \u201cLinear expected-time algorithms for connectivity problems\u201d, Proc. of the 11th. annual ACM Symp. on Theory of Computing, 368\u2013377, 1980.","DOI":"10.1145\/800141.804686"},{"key":"8_CR14","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. Comp. Sci., 48, 1986, 273\u2013281.","journal-title":"Theoret. Comp. Sci."},{"key":"8_CR15","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, Inf. Proc. Lett., 28, 1988, 5\u201311.","journal-title":"Inf. Proc. Lett."},{"key":"8_CR16","doi-asserted-by":"crossref","unstructured":"J.A. La Poutr\u00e9, \u201cMaintenance of triconnected components of graphs\u201d, Proc. 19th Int. Coll. Automata Languages and Programming, Lect. Not. in Computer Sci., Springer Verlag, (1992), 354\u2013365.","DOI":"10.1007\/3-540-55719-9_87"},{"key":"8_CR17","first-page":"106","volume-title":"Lect. Not. in Computer Sci., vol. 314","author":"J. A. Poutr\u00e9 La","year":"1985","unstructured":"J.A. La Poutr\u00e9, J. van Leeuwen, \u201cMaintenance of transitive closure and transitive reduction of graphs\u201d, Proc Work. on Graph Theoretic concepts in Comp. Sci., Lect. Not. in Computer Sci., vol. 314, Springer Verlag, Berlin, 1985, 106\u2013120."},{"key":"8_CR18","unstructured":"H. Rohnert, \u201cA dynamization of the all-pairs least cost path problem\u201d, Proc. of the 2nd Symp. on Theoretical Aspects of Computer Science, Lect. Not. in Comp. Sci., vol. 182, Springer-Verlag, 1990."},{"key":"8_CR19","unstructured":"J.H. Reif, P.G. Spirakis, M. Yung, \u201cFully dynamic graph connectivity in logarithmic expected time\u201d, Alcom Technical Report, 1992."},{"key":"8_CR20","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1016\/0022-0000(86)90044-9","volume":"33","author":"M. Santha","year":"1986","unstructured":"M. Santha, U.V. Vazirani, \u201cGenerating quasi-random sequences from semi-random sources\u201d, Journal of Computer and Systems Science, 33:75\u201387,1986.","journal-title":"Journal of Computer and Systems Science"},{"key":"8_CR21","doi-asserted-by":"crossref","first-page":"245","DOI":"10.1145\/62.2160","volume":"31","author":"R. E. Tarjan","year":"1984","unstructured":"R.E. Tarjan, Jan van Leeuwen, \u201cWorst case analysis of set union algorithms\u201d, Journal of Assoc. Comput. Mach., 31 (1984), 245\u2013281.","journal-title":"Journal of Assoc. Comput. Mach."},{"key":"8_CR22","unstructured":"J. Westbrook, \u201cAlgorithms and data structures for dynamic graph problems\u201d, Ph.D. Dissertation, Tech. Rep. CS-TR-229-89, Dept. of Computer Science, Princeton University, 1989."}],"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_43.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,20]],"date-time":"2023-06-20T18:36:39Z","timestamp":1687286199000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-57899-4_43"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994]]},"ISBN":["9783540578994","9783540483854"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/3-540-57899-4_43","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1994]]}}}