Subquadratic Algorithm for Dynamic Shortest Distances

These algorithms are used to construct an algorithm for dynamic shortest distances in unweighted graph and improve over the previous results and solve a long-standing open problem if sub-quadratic dynamic algorithms exist for computing all pairs shortest distances.

Abstract

In this paper we extend a technique introduced in [14] for dynamic matrix functions. We present dynamic algorithms for computing matrix determinant and matrix adjoint over commutative rings. These algorithms are then used to construct an algorithm for dynamic shortest distances in unweighted graph. Our algorithm supports updates in O(n 1.932) randomized time and queries in O(n 1.288) randomized time. These bound improve over the previous results and solve a long-standing open problem if sub-quadratic dynamic algorithms exist for computing all pairs shortest distances.