{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T06:19:38Z","timestamp":1725517178941},"publisher-location":"Berlin, Heidelberg","reference-count":79,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540852377"},{"type":"electronic","value":"9783540852384"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-85238-4_5","type":"book-chapter","created":{"date-parts":[[2008,8,18]],"date-time":"2008-08-18T15:34:36Z","timestamp":1219073676000},"page":"68-82","source":"Crossref","is-referenced-by-count":1,"title":["Algebraic Graph Algorithms"],"prefix":"10.1007","author":[{"given":"Piotr","family":"Sankowski","sequence":"first","affiliation":[]}],"member":"297","reference":[{"issue":"4","key":"5_CR1","doi-asserted-by":"publisher","first-page":"615","DOI":"10.1016\/0196-6774(91)90036-X","volume":"12","author":"G. Ausiello","year":"1991","unstructured":"Ausiello, G., Italiano, G.F., Marchetti Spaccamela, A., Nanni, U.: Incremental algorithms for minimal length paths. J. Algorithms\u00a012(4), 615\u2013638 (1991)","journal-title":"J. Algorithms"},{"key":"5_CR2","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1145\/509907.509928","volume-title":"Proceedings of the thiry-fourth annual ACM symposium on Theory of Computing","author":"S. Baswana","year":"2002","unstructured":"Baswana, S., Hariharan, R., Sen, S.: Improved decremental algorithms for maintaining transitive closure and all-pairs shortest paths. In: Proceedings of the thiry-fourth annual ACM symposium on Theory of Computing, pp. 117\u2013123. ACM Press, New York (2002)"},{"issue":"1","key":"5_CR3","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1090\/qam\/102435","volume":"16","author":"R. Bellman","year":"1958","unstructured":"Bellman, R.: On a Routing Problem. Quarterly of Applied Mathematics\u00a016(1), 87\u201390 (1958)","journal-title":"Quarterly of Applied Mathematics"},{"key":"5_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"586","DOI":"10.1007\/BFb0032060","volume-title":"Proc.17th ICALP","author":"N. Blum","year":"1990","unstructured":"Blum, N.: A new approach to maximum matching in general graphs. In: Proc.17th ICALP. LNCS, vol.\u00a0443, pp. 586\u2013597. Springer, Heidelberg (1990)"},{"key":"5_CR5","series-title":"Lecture Notes in Computer Science","volume-title":"Automata, Languages and Programming","year":"2006","unstructured":"Bugliesi, M., Preneel, B., Sassone, V., Wegener, I. (eds.): ICALP 2006. LNCS, vol.\u00a04051. Springer, Heidelberg (2006)"},{"key":"5_CR6","first-page":"335","volume-title":"SODA 1992: Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms","author":"J. Cheriyan","year":"1992","unstructured":"Cheriyan, J., Reif, J.H.: Directed s-t numberings, rubber bands, and testing digraph k-vertex connectivity. In: SODA 1992: Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms, pp. 335\u2013344. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA (1992)"},{"key":"5_CR7","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/28395.28396","volume-title":"Proceedings of the nineteenth annual ACM conference on Theory of computing","author":"D. Coppersmith","year":"1987","unstructured":"Coppersmith, D., Winograd, S.: Matrix multiplication via arithmetic progressions. In: Proceedings of the nineteenth annual ACM conference on Theory of computing, pp. 1\u20136. ACM Press, New York (1987)"},{"key":"5_CR8","doi-asserted-by":"crossref","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 (2000)","DOI":"10.1109\/SFCS.2000.892126"},{"key":"5_CR9","doi-asserted-by":"crossref","unstructured":"Demetrescu, C., Italiano, G.F.: Fully Dynamic All Pairs Shortest Paths with Real Edge Weights. In: Proceedings of 42th annual IEEE Symposium on Foundations of Computer Science, pp. 260\u2013267 (2001)","DOI":"10.1109\/SFCS.2001.959900"},{"key":"5_CR10","doi-asserted-by":"publisher","first-page":"633","DOI":"10.1007\/3-540-45465-9_54","volume-title":"Proceedings of the 29th International Colloquium on Automata, Languages and Programming","author":"C. Demetrescu","year":"2002","unstructured":"Demetrescu, C., Italiano, G.F.: Improved Bounds and New Trade-Offs for Dynamic All Pairs Shortest Paths. In: Proceedings of the 29th International Colloquium on Automata, Languages and Programming, pp. 633\u2013643. Springer, Heidelberg (2002)"},{"key":"5_CR11","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1145\/780542.780567","volume-title":"Proceedings of the thirty-fifth annual ACM Symposium on Theory of Computing","author":"C. Demetrescu","year":"2003","unstructured":"Demetrescu, C., Italiano, G.F.: A new approach to dynamic all pairs shortest paths. In: Proceedings of the thirty-fifth annual ACM Symposium on Theory of Computing, pp. 159\u2013166. ACM Press, New York (2003)"},{"key":"5_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"594","DOI":"10.1007\/978-3-540-75520-3_53","volume-title":"Algorithms \u2013 ESA 2007","author":"K. Diks","year":"2007","unstructured":"Diks, K., Sankowski, P.: Dynamic Plane Transitive Closure. In: Arge, L., Hoffmann, M., Welzl, E. (eds.) ESA 2007. LNCS, vol.\u00a04698, pp. 594\u2013604. Springer, Heidelberg (2007)"},{"key":"5_CR13","first-page":"1324","volume":"10","author":"E.A. Dinic","year":"1969","unstructured":"Dinic, E.A., Kronrod, M.A.: An Algorithm for the Solution of the Assignment Problem. Soviet Math. Dokl.\u00a010, 1324\u20131326 (1969)","journal-title":"Soviet Math. Dokl."},{"issue":"2","key":"5_CR14","doi-asserted-by":"publisher","first-page":"248","DOI":"10.1145\/321694.321699","volume":"19","author":"J. Edmonds","year":"1972","unstructured":"Edmonds, J., Karp, R.M.: Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems. J. ACM\u00a019(2), 248\u2013264 (1972)","journal-title":"J. ACM"},{"key":"5_CR15","first-page":"371","volume":"49","author":"S. Even","year":"1985","unstructured":"Even, S., Gazit, H.: Updating Distances in Dynamic Graphs. Methods of Operations Research\u00a049, 371\u2013387 (1985)","journal-title":"Methods of Operations Research"},{"key":"5_CR16","doi-asserted-by":"crossref","first-page":"232","DOI":"10.1109\/SFCS.2001.959897","volume-title":"Proceedings of the 42nd IEEE symposium on Foundations of Computer Science","author":"J. Fakcharoenphol","year":"2001","unstructured":"Fakcharoenphol, J.: Planar Graphs, Negative Weight Edges, Shortest Paths, and Near Linear Time. In: Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, pp. 232\u2013241. IEEE Computer Society Press, Los Alamitos (2001)"},{"key":"5_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-49116-3_34","volume-title":"STACS 99","author":"G.S. Frandsen","year":"1999","unstructured":"Frandsen, G.S., Hansen, J.P., Miltersen, P.B.: Lower Bounds for Dynamic Algebraic Problems. In: Meinel, C., Tison, S. (eds.) STACS 1999. LNCS, vol.\u00a01563. Springer, Heidelberg (1999)"},{"key":"5_CR18","doi-asserted-by":"crossref","unstructured":"Frandsen, G.S., Frandsen, P.F.: Dynamic matrix rank. In: Bugliesi, et al. (eds.) [5], pp. 395\u2013406","DOI":"10.1007\/11786986_35"},{"key":"5_CR19","volume-title":"ICALP Proc.\u00a035th ICALP","author":"G.S. Frandsen","year":"2008","unstructured":"Frandsen, G.S., Sankowski, P.: Dynamic normal forms and dynamic characteristic polynomial. In: ICALP Proc.\u00a035th ICALP. Springer, Heidelberg (2008)"},{"issue":"1","key":"5_CR20","doi-asserted-by":"publisher","first-page":"250","DOI":"10.1145\/322290.322305","volume":"29","author":"M.L. Fredman","year":"1982","unstructured":"Fredman, M.L.: The Complexity of Maintaining an Array and Computing Its Partial Sums. J. ACM\u00a029(1), 250\u2013260 (1982)","journal-title":"J. ACM"},{"issue":"3","key":"5_CR21","doi-asserted-by":"publisher","first-page":"250","DOI":"10.1007\/PL00009224","volume":"22","author":"D. Frigioni","year":"1998","unstructured":"Frigioni, D., Marchetti-Spaccamela, A., Nanni, U.: Semi-dynamic Algorithms for Maintaining Single Source Shortest Paths Trees. Algorithmica\u00a022(3), 250\u2013274 (1998)","journal-title":"Algorithmica"},{"issue":"2","key":"5_CR22","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1006\/jagm.1999.1048","volume":"34","author":"D. Frigioni","year":"2000","unstructured":"Frigioni, D., Marchetti-Spaccamela, A., Nanni, U.: Fully Dynamic Algorithms for Maintaining Shortest Paths Trees. J. Algorithms\u00a034(2), 251\u2013281 (2000)","journal-title":"J. Algorithms"},{"key":"5_CR23","doi-asserted-by":"publisher","first-page":"410","DOI":"10.1109\/SFCS.2000.892129","volume-title":"FOCS 2000: Proceedings of the 41st Annual Symposium on Foundations of Computer Science","author":"H.N. Gabow","year":"2000","unstructured":"Gabow, H.N.: Using expander graphs to find vertex connectivity. In: FOCS 2000: Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p. 410. IEEE Computer Society, Washington, DC, USA (2000)"},{"issue":"2","key":"5_CR24","doi-asserted-by":"publisher","first-page":"148","DOI":"10.1016\/0022-0000(85)90039-X","volume":"31","author":"H.N. Gabow","year":"1985","unstructured":"Gabow, H.N.: Scaling Algorithms for Network Problems. J. Comput. Syst. Sci.\u00a031(2), 148\u2013168 (1985)","journal-title":"J. Comput. Syst. Sci."},{"issue":"5","key":"5_CR25","doi-asserted-by":"publisher","first-page":"1013","DOI":"10.1137\/0218069","volume":"18","author":"H.N. Gabow","year":"1989","unstructured":"Gabow, H.N., Tarjan, R.E.: Faster Scaling Algorithms for Network Problems. SIAM J. Comput.\u00a018(5), 1013\u20131036 (1989)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"5_CR26","doi-asserted-by":"publisher","first-page":"815","DOI":"10.1145\/115234.115366","volume":"38","author":"H.N. Gabow","year":"1991","unstructured":"Gabow, H.N., Tarjan, R.E.: Faster scaling algorithms for general graph matching problems. J. ACM\u00a038(4), 815\u2013853 (1991)","journal-title":"J. ACM"},{"key":"5_CR27","unstructured":"Andrew, V.: Scaling algorithms for the shortest paths problem. In: SODA 1993: Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, pp. 222\u2013231.Society for Industrial and Applied Mathematics (1993)"},{"key":"5_CR28","first-page":"531","volume-title":"FOCS 2006: Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science","author":"J.A. Nicholas","year":"2006","unstructured":"Nicholas, J.A.: Algebraic structures and algorithms for matching and matroid problems. In: FOCS 2006: Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, pp. 531\u2013542. IEEE Computer Society, Washington, DC, USA (2006)"},{"key":"5_CR29","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"},{"issue":"1","key":"5_CR30","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1006\/jcss.1997.1493","volume":"55","author":"M.R. Henzinger","year":"1997","unstructured":"Henzinger, M.R., Klein, P., Rao, S., Subramanian, S.: Faster Shortest-path Algorithms for Planar Graphs. J. Comput. Syst. Sci.\u00a055(1), 3\u201323 (1997)","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"5_CR31","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1006\/jcom.1998.0476","volume":"14","author":"X. Huang","year":"1998","unstructured":"Huang, X., Pan, V.Y.: Fast Rectangular Matrix Multiplication and Applications. Journal of complexity\u00a014(2), 257\u2013299 (1998)","journal-title":"Journal of complexity"},{"key":"5_CR32","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1016\/0020-0190(83)90033-9","volume":"16","author":"T. Ibaraki","year":"1983","unstructured":"Ibaraki, T., Katoh, N.: On-line Computation of Transitive Closure for Graphs. Inform. Proc. Lett.\u00a016, 95\u201397 (1983)","journal-title":"Inform. Proc. Lett."},{"key":"5_CR33","first-page":"27","volume":"3","author":"M. Iri","year":"1960","unstructured":"Iri, M.: A new method for solving transportation-network problems. Journal of the Operations Research Society of Japan\u00a03, 27\u201387 (1960)","journal-title":"Journal of the Operations Research Society of Japan"},{"issue":"2-3","key":"5_CR34","doi-asserted-by":"publisher","first-page":"273","DOI":"10.1016\/0304-3975(86)90098-8","volume":"48","author":"G.F. Italiano","year":"1986","unstructured":"Italiano, G.F.: Amortized Efficiency of a Path Retrieval Data Structure. Theor. Comput. Sci.\u00a048(2-3), 273\u2013281 (1986)","journal-title":"Theor. Comput. Sci."},{"key":"5_CR35","unstructured":"Ford Jr., L.R.: Network Flow Theory. Paper P-923, The RAND Corperation, Santa Moncia, California (August 1956)"},{"key":"5_CR36","doi-asserted-by":"crossref","unstructured":"Kao, M.-Y., Lam, T.W., Sung, W.-K., Ting, H.-F.: A decomposition theorem for maximum weight bipartite matchings with applications to evolutionary trees. In: Proceedings of the 7th Annual European Symposium on Algorithms, pp. 438\u2013449 (1999)","DOI":"10.1007\/3-540-48481-7_38"},{"issue":"1","key":"5_CR37","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1007\/BF02579407","volume":"6","author":"R.M. Karp","year":"1986","unstructured":"Karp, R.M., Upfal, E., Wigderson, A.: Constructing a perfect matching is in random nc. Combinatorica\u00a06(1), 35\u201348 (1986)","journal-title":"Combinatorica"},{"key":"5_CR38","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":"5_CR39","doi-asserted-by":"crossref","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 (1999)","DOI":"10.1109\/SFFCS.1999.814580"},{"key":"5_CR40","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":"5_CR41","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1002\/nav.3800020109","volume":"2","author":"H.W. Kuhn","year":"1955","unstructured":"Kuhn, H.W.: The Hungarian Method for the Assignment Problem. Naval Research Logistics Quarterly\u00a02, 83\u201397 (1955)","journal-title":"Naval Research Logistics Quarterly"},{"key":"5_CR42","series-title":"Lecture Notes in Computer Science","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","author":"J.A. La Poutr\u00e9","year":"1988","unstructured":"La Poutr\u00e9, J.A., van Leeuwen, J.: Maintenance of Transitive Closure and Transitive Reduction of Graphs. In: Proc. Workshop on Graph-Theoretic Concepts in Computer Science. LNCS, vol.\u00a0314, pp. 106\u2013120. Springer, Berlin (1988)"},{"issue":"3","key":"5_CR43","doi-asserted-by":"publisher","first-page":"615","DOI":"10.1137\/0209046","volume":"9","author":"R.J. Lipton","year":"1980","unstructured":"Lipton, R.J., Tarjan, R.E.: Applications of a planar separator theorem. SIAM J. Comput.\u00a09(3), 615\u2013627 (1980)","journal-title":"SIAM J. Comput."},{"key":"5_CR44","first-page":"96","volume":"205","author":"P. Loubal","year":"1967","unstructured":"Loubal, P.: A Network Evaluation Procedure. Highway Research Record\u00a0205, 96\u2013109 (1967)","journal-title":"Highway Research Record"},{"key":"5_CR45","doi-asserted-by":"crossref","unstructured":"Micali, S., Vazirani, V.V.: An $O(\\sqrt{|V|}|E|)$ algorithm for finding maximum matching in general graphs. In: Proceedings of the twenty first annual IEEE Symposium on Foundations of Computer Science, pp. 17\u201327 (1980)","DOI":"10.1109\/SFCS.1980.12"},{"issue":"5","key":"5_CR46","doi-asserted-by":"publisher","first-page":"1002","DOI":"10.1137\/S0097539789162997","volume":"24","author":"G.L. Miller","year":"1995","unstructured":"Miller, G.L., Naor, J.: Flow in planar graphs with multiple sources and sinks. SIAM J. Comput.\u00a024(5), 1002\u20131017 (1995)","journal-title":"SIAM J. Comput."},{"key":"5_CR47","unstructured":"Moore, E.F.: The Shortest Path Through a Maze. In: Proceedings of the International Symposium on the Theory of Switching, pp. 285\u2013292. Harvard University Press (1959)"},{"key":"5_CR48","doi-asserted-by":"crossref","unstructured":"Mucha, M., Sankowski, P.: Maximum Matchings in Planar Graphs via Gaussian Elimination. In: Proceedings of 12th annual European Symposium on Algorithms, pp. 532\u2013543 (2004)","DOI":"10.1007\/978-3-540-30140-0_48"},{"key":"5_CR49","doi-asserted-by":"crossref","unstructured":"Mucha, M., Sankowski, P.: Maximum Matchings via Gaussian Elimination. In: Proceedings of the 45th annual IEEE Symposium on Foundations of Computer Science, pp. 248\u2013255 (2004)","DOI":"10.1109\/FOCS.2004.40"},{"key":"5_CR50","doi-asserted-by":"crossref","unstructured":"Mucha, M., Sankowski, P.: Maximum matchings via gaussian elimination. In: Proceedings of the 45th annual IEEE Symposium on Foundations of Computer Science, pp. 248\u2013255 (2004)","DOI":"10.1109\/FOCS.2004.40"},{"key":"5_CR51","doi-asserted-by":"crossref","unstructured":"Mucha, M., Sankowski, P.: Fast dynamic transitive closure with lookahead. Algorithmica (2008)","DOI":"10.1007\/s00453-008-9166-2"},{"key":"5_CR52","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1145\/28395.383347","volume-title":"STOC 1987: Proceedings of the nineteenth annual ACM conference on Theory of computing","author":"K. Mulmuley","year":"1987","unstructured":"Mulmuley, K., Vazirani, U.V., Vazirani, V.V.: Matching is as easy as matrix inversion. In: STOC 1987: Proceedings of the nineteenth annual ACM conference on Theory of computing, pp. 345\u2013354. ACM Press, New York (1987)"},{"issue":"1","key":"5_CR53","first-page":"32","volume":"5","author":"J. Munkres","year":"1957","unstructured":"Munkres, J.: Algorithms for the Assignment and Transportation Problems. Journal of SIAM\u00a05(1), 32\u201338 (1957)","journal-title":"Journal of SIAM"},{"key":"5_CR54","unstructured":"Murchland, J.: The Effect of Increasing or Decreasing the Length of a Single Arc on All Shortest Distances in a Graph. Technical report, LBS-TNT-26 (1967)"},{"key":"5_CR55","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1007\/BF02122557","volume":"8","author":"L. Lov\u00e1sz","year":"1988","unstructured":"Lov\u00e1sz, L., Linial, N., Wigderson, A.: Rubber bands, convex embeddings and graph connectivity. Combinatorica\u00a08, 91\u2013102 (1988)","journal-title":"Combinatorica"},{"key":"5_CR56","doi-asserted-by":"publisher","first-page":"557","DOI":"10.1016\/0196-6774(89)90005-9","volume":"10","author":"M.O. Rabin","year":"1989","unstructured":"Rabin, M.O., Vazirani, V.V.: Maximum matchings in general graphs through randomization. Journal of Algorithms\u00a010, 557\u2013567 (1989)","journal-title":"Journal of Algorithms"},{"issue":"2","key":"5_CR57","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1006\/jagm.1996.0046","volume":"21","author":"G. Ramalingam","year":"1996","unstructured":"Ramalingam, G., Reps, T.: An Incremental Algorithm for a Generalization of the Shortest-path Problem. J. Algorithms\u00a021(2), 267\u2013305 (1996)","journal-title":"J. Algorithms"},{"issue":"1-2","key":"5_CR58","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1016\/0304-3975(95)00079-8","volume":"158","author":"G. Ramalingam","year":"1996","unstructured":"Ramalingam, G., Reps, T.: On the Computational Complexity of Dynamic Graph Problems. Theor. Comput. Sci.\u00a0158(1-2), 233\u2013277 (1996)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"5_CR59","doi-asserted-by":"publisher","first-page":"347","DOI":"10.1006\/jagm.1995.0807","volume":"22","author":"J.H. Reif","year":"1997","unstructured":"Reif, J.H., Tate, S.R.: On Dynamic Algorithms for Algebraic Problems. J. Algorithms\u00a022(2), 347\u2013371 (1997)","journal-title":"J. Algorithms"},{"issue":"5","key":"5_CR60","doi-asserted-by":"publisher","first-page":"336","DOI":"10.1016\/0041-5553(68)90148-1","volume":"8","author":"V. Rodionov","year":"1968","unstructured":"Rodionov, V.: The Parametric Problem of Shortest Distances. U.S.S.R. Computational Math. and Math. Phys.\u00a08(5), 336\u2013343 (1968)","journal-title":"U.S.S.R. Computational Math. and Math. Phys."},{"key":"5_CR61","unstructured":"Roditty, L.: A Faster and Simpler Fully Dynamic Transitive Closure. In: Proceedings of the fourteenth annual ACM-SIAM Symposium on Discrete Algorithms, pp. 404\u2013412. Society for Industrial and Applied Mathematics (2003)"},{"key":"5_CR62","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, Los Alamitos (2002)"},{"key":"5_CR63","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":"5_CR64","first-page":"279","volume-title":"Proceedings of the 2nd Symposium of Theoretical Aspects of Computer Science","author":"H. Rohnert","year":"1985","unstructured":"Rohnert, H.: A Dynamization of the All Pairs Least Cost Path Problem. In: Proceedings of the 2nd Symposium of Theoretical Aspects of Computer Science, pp. 279\u2013286. Springer, Heidelberg (1985)"},{"key":"5_CR65","doi-asserted-by":"crossref","unstructured":"Sankowski, P.: Dynamic Transitive Closure via Dynamic Matrix Inverse. In: Proceedings of the 45th annual IEEE Symposium on Foundations of Computer Science, pp. 509\u2013517 (2004)","DOI":"10.1109\/FOCS.2004.25"},{"key":"5_CR66","volume-title":"SPAA 2005: Proceedings of the seventeenth annual ACM symposium on Parallelism in algorithms and architectures","author":"P. Sankowski","year":"2005","unstructured":"Sankowski, P.: Processor efficient parallel matching. In: SPAA 2005: Proceedings of the seventeenth annual ACM symposium on Parallelism in algorithms and architectures. ACM Press, New York, NY, USA (2005)"},{"key":"5_CR67","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"770","DOI":"10.1007\/11561071_68","volume-title":"Algorithms \u2013 ESA 2005","author":"P. Sankowski","year":"2005","unstructured":"Sankowski, P.: Shortest Paths in Matrix Multiplication Time. In: Brodal, G.S., Leonardi, S. (eds.) ESA 2005. LNCS, vol.\u00a03669, pp. 770\u2013778. Springer, Heidelberg (2005)"},{"key":"5_CR68","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"461","DOI":"10.1007\/11533719_47","volume-title":"Computing and Combinatorics","author":"P. Sankowski","year":"2005","unstructured":"Sankowski, P.: Subquadratic Algorithm for Dynamic Shortest Distances. In: Wang, L. (ed.) COCOON 2005. LNCS, vol.\u00a03595, pp. 461\u2013470. Springer, Heidelberg (2005)"},{"key":"5_CR69","doi-asserted-by":"crossref","unstructured":"Sankowski, P.: Weighted bipartite matching in matrix multiplication time. In: Bugliesi, et al. (eds.) [5], pp. 274\u2013285","DOI":"10.1007\/11786986_25"},{"key":"5_CR70","first-page":"118","volume-title":"SODA 2007: Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms","author":"P. Sankowski","year":"2007","unstructured":"Sankowski, P.: Faster dynamic matchings and vertex connectivity. In: SODA 2007: Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, pp. 118\u2013126. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA (2007)"},{"issue":"5","key":"5_CR71","first-page":"621","volume":"20","author":"J. Sherman","year":"1949","unstructured":"Sherman, J., Morrison, W.J.: Adjustment of an inverse matrix corresponding to changes in the elements of a given column or a given row of the original matrix. Ann. Math. Statist.\u00a020(5), 621 (1949)","journal-title":"Ann. Math. Statist."},{"issue":"1","key":"5_CR72","doi-asserted-by":"publisher","first-page":"124","DOI":"10.1214\/aoms\/1177729893","volume":"21","author":"J. Sherman","year":"1950","unstructured":"Sherman, J., Morrison, W.J.: Adjustment of an inverse matrix corresponding to a change in one element of a given matrix. Ann. Math. Statist.\u00a021(1), 124\u2013127 (1950)","journal-title":"Ann. Math. Statist."},{"key":"5_CR73","first-page":"199","volume-title":"Proceedings of the Symposium on Information Networks","author":"A. Shimbel","year":"1955","unstructured":"Shimbel, A.: Structure in Communication Nets. In: Proceedings of the Symposium on Information Networks, pp. 199\u2013203. Polytechnic Press of the Polytechnic Institute of Brooklyn, Brooklyn (1955)"},{"issue":"3-4","key":"5_CR74","doi-asserted-by":"publisher","first-page":"613","DOI":"10.1016\/S0747-7171(03)00097-X","volume":"36","author":"A. Storjohann","year":"2003","unstructured":"Storjohann, A.: High-order lifting and integrality certification. J. Symb. Comput.\u00a036(3-4), 613\u2013648 (2003)","journal-title":"J. Symb. Comput."},{"key":"5_CR75","first-page":"372","volume-title":"ESA 1993: Proceedings of the First Annual European Symposium on Algorithms","author":"S. Subramanian","year":"1993","unstructured":"Subramanian, S.: A fully dynamic data structure for reachability in planar digraphs. In: ESA 1993: Proceedings of the First Annual European Symposium on Algorithms, pp. 372\u2013383. Springer, London, UK (1993)"},{"key":"5_CR76","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"384","DOI":"10.1007\/978-3-540-27810-8_33","volume-title":"Algorithm Theory - SWAT 2004","author":"M. Thorup","year":"2004","unstructured":"Thorup, M.: Fully-dynamic all-pairs shortest paths: Faster and allowing negative cycles. In: Hagerup, T., Katajainen, J. (eds.) SWAT 2004. LNCS, vol.\u00a03111, pp. 384\u2013396. Springer, Heidelberg (2004)"},{"key":"5_CR77","doi-asserted-by":"publisher","first-page":"112","DOI":"10.1145\/1060590.1060607","volume-title":"STOC 2005: Proceedings of the thirty-seventh annual ACM symposium on Theory of computing","author":"M. Thorup","year":"2005","unstructured":"Thorup, M.: Worst-case update times for fully-dynamic all-pairs shortest paths. In: STOC 2005: Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, pp. 112\u2013119. ACM, New York, NY, USA (2005)"},{"key":"5_CR78","doi-asserted-by":"publisher","first-page":"369","DOI":"10.1007\/BF01209711","volume":"30","author":"D.M. Yellin","year":"1993","unstructured":"Yellin, D.M.: Speeding up Dynamic Transitive Closure for Bounded Degree Graphs. Acta Informatica\u00a030, 369\u2013384 (1993)","journal-title":"Acta Informatica"},{"key":"5_CR79","first-page":"389","volume-title":"FOCS","author":"R. Yuster","year":"2005","unstructured":"Yuster, R., Zwick, U.: Answering distance queries in directed graphs using fast matrix multiplication. In: FOCS, pp. 389\u2013396. IEEE Computer Society, Los Alamitos (2005)"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2008"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-85238-4_5.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,24]],"date-time":"2020-11-24T02:23:30Z","timestamp":1606184610000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-85238-4_5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540852377","9783540852384"],"references-count":79,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-85238-4_5","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[]}}