{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T23:16:55Z","timestamp":1725491815754},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540755197"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-75520-3_53","type":"book-chapter","created":{"date-parts":[[2007,9,14]],"date-time":"2007-09-14T03:46:33Z","timestamp":1189741593000},"page":"594-604","source":"Crossref","is-referenced-by-count":3,"title":["Dynamic Plane Transitive Closure"],"prefix":"10.1007","author":[{"given":"Krzysztof","family":"Diks","sequence":"first","affiliation":[]},{"given":"Piotr","family":"Sankowski","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"53_CR1","doi-asserted-by":"crossref","first-page":"381","DOI":"10.1109\/SFCS.2000.892126","volume-title":"Proceedings of 41th annual IEEE Symposium on Foundations of Computer Science","author":"C. Demetrescu","year":"2000","unstructured":"Demetrescu, C., Italiano, G.F.: Fully Dynamic Transitive Closure: Breaking Through the O(n 2) Barrier. In: Proceedings of 41th annual IEEE Symposium on Foundations of Computer Science, pp. 381\u2013389. IEEE Computer Society Press, Los Alamitos (2000)"},{"key":"53_CR2","doi-asserted-by":"publisher","first-page":"208","DOI":"10.1145\/167088.167159","volume-title":"STOC 1993","author":"D. Eppstein","year":"1993","unstructured":"Eppstein, D., Galil, Z., Italiano, G.F., Spencer, T.H.: Separator based sparsification for dynamic planar graph algorithms. In: STOC 1993. Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, pp. 208\u2013217. ACM Press, New York, USA (1993)"},{"issue":"5","key":"53_CR3","doi-asserted-by":"publisher","first-page":"868","DOI":"10.1016\/j.jcss.2005.05.007","volume":"72","author":"J. Fakcharoenphol","year":"2006","unstructured":"Fakcharoenphol, J., Rao, S.: Planar graphs, negative weight edges, shortest paths, and near linear time. J. Comput. Syst. Sci.\u00a072(5), 868\u2013889 (2006)","journal-title":"J. Comput. Syst. Sci."},{"key":"53_CR4","doi-asserted-by":"crossref","unstructured":"Henzinger, M.R., King, V.: Fully Dynamic Biconnectivity and Transitive Closure. In: Proceedings 36th annual IEEE Symposiumon Foundations of Computer Science, pp. 664\u2013672 (1995)","DOI":"10.1109\/SFCS.1995.492668"},{"key":"53_CR5","doi-asserted-by":"crossref","unstructured":"Husfeldt, T.: Fully dynamic transitive closure in plane dags with one source and one sink. In: European Symposium on Algorithms, pp. 199\u2013212 (1995)","DOI":"10.1007\/3-540-60313-1_144"},{"key":"53_CR6","doi-asserted-by":"crossref","unstructured":"Khanna, S., Motwani, R., Wilson, R.H.: On Certificates and Lookahead on Dynamic Graph Problems. In: Proceedings 7th annual ACM-SIAM Symposiumon on Discrete Algorithms, pp. 222\u2013231 (1996)","DOI":"10.2172\/93769"},{"key":"53_CR7","first-page":"81","volume-title":"Proceedings of 40th annual IEEE 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: Proceedings of 40th annual IEEE Symposium on Foundations of Computer Science, pp. 81\u201391. IEEE Computer Society Press, Los Alamitos (1999)"},{"key":"53_CR8","doi-asserted-by":"publisher","first-page":"492","DOI":"10.1145\/301250.301380","volume-title":"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: Proceedings of the thirty-first annual ACM Symposium on Theory of Computing, pp. 492\u2013498. ACM Press, New York (1999)"},{"key":"53_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"442","DOI":"10.1007\/3-540-57155-8_269","volume-title":"Algorithms and Data Structures","author":"P.N. Klein","year":"1993","unstructured":"Klein, P.N., Subramanian, S.: A fully dynamic approximation scheme for all-pairs shortest paths in planar graphs. In: Dehne, F., Sack, J.-R., Santoro, N. (eds.) WADS 1993. LNCS, vol.\u00a0709, pp. 442\u2013451. Springer, Heidelberg (1993)"},{"key":"53_CR10","doi-asserted-by":"crossref","unstructured":"Lipton, R.J., Tarjan, R.E.: A separator theorem for planar graphs. SIAM J. Applied Math., 177\u2013189 (1979)","DOI":"10.1137\/0136016"},{"key":"53_CR11","doi-asserted-by":"publisher","first-page":"376","DOI":"10.1145\/800057.808703","volume-title":"STOC 1984","author":"G.L. Miller","year":"1984","unstructured":"Miller, G.L.: Finding small simple cycle separators for 2-connected planar graphs. In: STOC 1984. Proceedings of the sixteenth annual ACM symposium on Theory of computing, pp. 376\u2013382. ACM Press, New York (1984)"},{"key":"53_CR12","series-title":"Society for Industrial and Applied Mathematics","first-page":"404","volume-title":"Proceedings of the fourteenth annual ACM-SIAM Symposium on Discrete Algorithms","author":"L. Roditty","year":"2003","unstructured":"Roditty, L.: A Faster and Simpler Fully Dynamic Transitive Closure. In: Proceedings of the fourteenth annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, pp. 404\u2013412. ACM Press, New York (2003)"},{"key":"53_CR13","first-page":"679","volume-title":"Proceedings of the 43rd Symposium on Foundations of Computer Science","author":"L. Roditty","year":"2002","unstructured":"Roditty, L., Zwick, U.: Improved Dynamic Reachability Algorithms for Directed Graphs. In: Proceedings of the 43rd Symposium on Foundations of Computer Science, p. 679. IEEE Computer Society Press, Los Alamitos (2002)"},{"key":"53_CR14","first-page":"184","volume-title":"Proceeding of the 36th annual ACM Symposium on Theory of Computing","author":"L. Roditty","year":"2004","unstructured":"Roditty, L., Zwick, U.: A Fully Dynamic Reachability Algorithm for Directed Graphs with an Almost Linear Update Time. In: Proceeding of the 36th annual ACM Symposium on Theory of Computing, pp. 184\u2013191. ACM Press, New York (2004)"},{"key":"53_CR15","first-page":"248","volume-title":"Proceedings of the 45th annual IEEE Symposium on Foundations of Computer Science","author":"P. Sankowski","year":"2004","unstructured":"Sankowski, P.: Dynamic transitive closure via dynamic matrix inverse. In: Proceedings of the 45th annual IEEE Symposium on Foundations of Computer Science, pp. 248\u2013255. IEEE Computer Society Press, Los Alamitos (2004)"},{"key":"53_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"372","DOI":"10.1007\/3-540-57273-2_72","volume-title":"Algorithms - ESA \u201993","author":"S. Subramanian","year":"1993","unstructured":"Subramanian, S.: A fully dynamic data structure for reachability in planar digraphs. In: Lengauer, T. (ed.) ESA 1993. LNCS, vol.\u00a0726, pp. 372\u2013383. Springer, Heidelberg (1993)"},{"issue":"6","key":"53_CR17","doi-asserted-by":"publisher","first-page":"993","DOI":"10.1145\/1039488.1039493","volume":"51","author":"M. Thorup","year":"2004","unstructured":"Thorup, M.: Compact oracles for reachability and approximate distances in planar digraphs. J. ACM\u00a051(6), 993\u20131024 (2004)","journal-title":"J. ACM"},{"issue":"1","key":"53_CR18","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1145\/1077464.1077466","volume":"1","author":"R. Yuster","year":"2005","unstructured":"Yuster, R., Zwick, U.: Fast sparse matrix multiplication. ACM Trans. Algorithms\u00a01(1), 2\u201313 (2005)","journal-title":"ACM Trans. Algorithms"}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2013 ESA 2007"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-75520-3_53.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T10:22:59Z","timestamp":1619518979000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-75520-3_53"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540755197"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-75520-3_53","relation":{},"subject":[]}}