Subquadratic Algorithm for Dynamic Shortest Distances Eztended 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(n1.932) randomized time and queries in O(n1.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.

作者: Piotr Sankowski

作者单位: Institute of Informatics, Warsaw University ul. Banacha 2, 02-097 Warsaw

会议类型: 国际会议

会议名称: The 11th Annual International Computing and Combinatorics Conference COCOON 2005(第11届国际计算和组合会议)

会议地点: 昆明

会议语种:英文

页码: 461-470

在线出版日期: 2005-08-01（万方平台首次上网日期，不代表论文的发表时间）