{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T17:56:04Z","timestamp":1725558964680},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642141645"},{"type":"electronic","value":"9783642141652"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-14165-2_18","type":"book-chapter","created":{"date-parts":[[2010,7,5]],"date-time":"2010-07-05T13:26:02Z","timestamp":1278336362000},"page":"201-212","source":"Crossref","is-referenced-by-count":4,"title":["New Data Structures for Subgraph Connectivity"],"prefix":"10.1007","author":[{"given":"Ran","family":"Duan","sequence":"first","affiliation":[]}],"member":"297","reference":[{"issue":"3","key":"18_CR1","doi-asserted-by":"publisher","first-page":"681","DOI":"10.1137\/S009753970343912X","volume":"36","author":"T. Chan","year":"2006","unstructured":"Chan, T.: Dynamic subgraph connectivity with geometric applications. SIAM J.\u00a0Comput.\u00a036(3), 681\u2013694 (2006)","journal-title":"SIAM J.\u00a0Comput."},{"key":"18_CR2","doi-asserted-by":"crossref","unstructured":"Chan, T.M., P\u01cetra\u015fcu, M., Roditty, L.: Dynamic connectivity: Connecting to networks and geometry. In: Proceedings 49th IEEE Symposium on Foundations of Computer Science (FOCS), pp. 95\u2013104 (2008)","DOI":"10.1109\/FOCS.2008.29"},{"key":"18_CR3","doi-asserted-by":"crossref","unstructured":"Coppersmith, D., Winograd, T.: Matrix multiplication via arithmetic progressions. In: Proc. 19th ACM Symp. on the Theory of Computing (STOC), pp. 1\u20136 (1987)","DOI":"10.1145\/28395.28396"},{"issue":"6","key":"18_CR4","first-page":"968","volume":"51","author":"C. Demetrescu","year":"2004","unstructured":"Demetrescu, C., Italiano, G.F.: A new approach to dynamic all pairs shortest paths. J.\u00a0ACM\u00a051(6), 968\u2013992 (2004)","journal-title":"J.\u00a0ACM"},{"issue":"5","key":"18_CR5","doi-asserted-by":"publisher","first-page":"1299","DOI":"10.1137\/S0097539705429847","volume":"37","author":"C. Demetrescu","year":"2008","unstructured":"Demetrescu, C., Thorup, M., Chowdhury, R.A., Ramachandran, V.: Oracles for distances avoiding a failed node or link. SIAM J.\u00a0Comput.\u00a037(5), 1299\u20131318 (2008)","journal-title":"SIAM J.\u00a0Comput."},{"issue":"2","key":"18_CR6","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1145\/1059513.1059514","volume":"52","author":"C. Demetrescu","year":"2005","unstructured":"Demetrescu, C., Italiano, G.F.: Trade-offs for fully dynamic transitive closure on dags: breaking through the o(n2 barrier. J. ACM\u00a052(2), 147\u2013156 (2005)","journal-title":"J. ACM"},{"key":"18_CR7","doi-asserted-by":"crossref","unstructured":"Duan, R., Pettie, S.: Dual-failure distance and connectivity oracles. In: Proceedings 20th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 506\u2013515 (2009)","DOI":"10.1137\/1.9781611973068.56"},{"key":"18_CR8","doi-asserted-by":"crossref","unstructured":"Duan, R., Pettie, S.: Connectivity oracles for failure prone graphs. In: Proceedings 42nd Annual ACM Symposium on Theory of Computing, STOC (to appear, 2010)","DOI":"10.1145\/1806689.1806754"},{"issue":"5","key":"18_CR9","first-page":"669","volume":"44","author":"D. Eppstein","year":"1997","unstructured":"Eppstein, D., Galil, Z., Italiano, G., Nissenzweig, A.: Sparsification \u2013 a technique for speeding up dynamic graph algorithms. J.\u00a0ACM\u00a044(5), 669\u2013696 (1997)","journal-title":"J.\u00a0ACM"},{"issue":"4","key":"18_CR10","doi-asserted-by":"publisher","first-page":"781","DOI":"10.1137\/0214055","volume":"14","author":"G. Frederickson","year":"1985","unstructured":"Frederickson, G.: Data structures for on-line updating of minimum spanning trees, with applications. SIAM J.\u00a0Comput.\u00a014(4), 781\u2013798 (1985)","journal-title":"SIAM J.\u00a0Comput."},{"issue":"1","key":"18_CR11","doi-asserted-by":"publisher","first-page":"76","DOI":"10.1007\/s004530010032","volume":"28","author":"D. Frigioni","year":"2000","unstructured":"Frigioni, D., Italiano, G.F.: Dynamically switching vertices in planar graphs. Algorithmica\u00a028(1), 76\u2013103 (2000)","journal-title":"Algorithmica"},{"issue":"4","key":"18_CR12","first-page":"502","volume":"46","author":"M. Henzinger","year":"1999","unstructured":"Henzinger, M., King, V.: Randomized fully dynamic graph algorithms with polylogarithmic time per operation. J.\u00a0ACM\u00a046(4), 502\u2013516 (1999)","journal-title":"J.\u00a0ACM"},{"issue":"4","key":"18_CR13","first-page":"723","volume":"48","author":"J. Holm","year":"2001","unstructured":"Holm, J., de Lichtenberg, K., Thorup, M.: Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity. J.\u00a0ACM\u00a048(4), 723\u2013760 (2001)","journal-title":"J.\u00a0ACM"},{"key":"18_CR14","volume-title":"FOCS 1999: Proceedings of the 40th Annual Symposium on Foundations of Computer Science","author":"V. King","year":"1999","unstructured":"King, V.: Fully dynamic algorithms for maintaining all-pairs shortest paths and transitive closure in digraphs. In: FOCS 1999: Proceedings of the 40th Annual Symposium on Foundations of Computer Science, Washington, DC, USA, IEEE Computer Society, Los Alamitos (1999)"},{"key":"18_CR15","doi-asserted-by":"publisher","first-page":"492","DOI":"10.1145\/301250.301380","volume-title":"STOC 1999: Proceedings of the thirty-first annual ACM symposium on Theory of computing","author":"V. King","year":"1999","unstructured":"King, V., Sagert, G.: A fully dynamic algorithm for maintaining the transitive closure. In: STOC 1999: Proceedings of the thirty-first annual ACM symposium on Theory of computing, pp. 492\u2013498. ACM, New York (1999)"},{"key":"18_CR16","doi-asserted-by":"crossref","unstructured":"P\u01cetra\u015fcu, M., Thorup, M.: Planning for fast connectivity updates. In: Proceedings 48th IEEE Symposium on Foundations of Computer Science (FOCS), pp. 263\u2013271 (2007)","DOI":"10.1109\/FOCS.2007.4389498"},{"key":"18_CR17","doi-asserted-by":"crossref","unstructured":"Roditty, L., Zwick, U.: A fully dynamic reachability algorithm for directed graphs with an almost linear update time. In: Proceedings 36th ACM Symposium on Theory of Computing (STOC), pp. 184\u2013191 (2004)","DOI":"10.1145\/1007352.1007387"},{"key":"18_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"580","DOI":"10.1007\/978-3-540-30140-0_52","volume-title":"Algorithms \u2013 ESA 2004","author":"L. Roditty","year":"2004","unstructured":"Roditty, L., Zwick, U.: On dynamic shortest paths problems. In: Albers, S., Radzik, T. (eds.) ESA 2004. LNCS, vol.\u00a03221, pp. 580\u2013591. Springer, Heidelberg (2004)"},{"issue":"5","key":"18_CR19","doi-asserted-by":"publisher","first-page":"1455","DOI":"10.1137\/060650271","volume":"37","author":"L. Roditty","year":"2008","unstructured":"Roditty, L., Zwick, U.: Improved dynamic reachability algorithms for directed graphs. SIAM J.\u00a0Comput.\u00a037(5), 1455\u20131471 (2008)","journal-title":"SIAM J.\u00a0Comput."},{"key":"18_CR20","doi-asserted-by":"crossref","unstructured":"Sankowski, P.: Dynamic transitive closure via dynamic matrix inverse. In: Proceedings 45th IEEE Symposium on Foundations of Computer Science (FOCS), pp. 509\u2013517 (2004)","DOI":"10.1109\/FOCS.2004.25"},{"issue":"2","key":"18_CR21","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1006\/jagm.1999.1033","volume":"33","author":"M. Thorup","year":"1999","unstructured":"Thorup, M.: Decremental dynamic connectivity. J.\u00a0Algor.\u00a033(2), 229\u2013243 (1999)","journal-title":"J.\u00a0Algor."},{"key":"18_CR22","doi-asserted-by":"crossref","unstructured":"Thorup, M.: Near-optimal fully-dynamic graph connectivity. In: Proceedings 32nd ACM Symposium on Theory of Computing (STOC), pp. 343\u2013350 (2000)","DOI":"10.1145\/335305.335345"},{"key":"18_CR23","doi-asserted-by":"crossref","unstructured":"Thorup, M.: Worst-case update times for fully-dynamic all-pairs shortest paths. In: Proceedings 37th ACM Symposium on Theory of Computing (STOC), pp. 112\u2013119 (2005)","DOI":"10.1145\/1060590.1060607"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-14165-2_18.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,24]],"date-time":"2020-11-24T02:48:15Z","timestamp":1606186095000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-14165-2_18"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642141645","9783642141652"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-14165-2_18","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}