Dynamic approximate all-pairs shortest paths: Breaking the O(mn) barrier and derandomization (2013)

Content Provider	CiteSeerX
Author	Henzinger, Monika Krinninger, Sebastian Nanongkai, Danupon
Description	We study dynamic (1 + )-approximation algorithms for the all-pairs shortest paths problem in unweighted undirected n-node m-edge graphs under edge deletions. The fastest algorithm for this problem is a randomized algorithm with a total update time of Õ(mn) and constant query time by Roditty and Zwick [33] (FOCS 2004). The fastest deterministic algorithm is from a 1981 paper by Even and Shiloach [23]; it has a total update time of O(mn2) and constant query time. We improve these results as follows: (1) We present an algorithm with a total update time of Õ(n5/2) and constant query time that has an additive error of two in addition to the 1 + multiplicative error. This beats the previous Õ(mn) time when m = Ω(n3/2). Note that the additive error is unavoidable since, even in the static case, an O(n3−δ)-time (a so-called truly subcubic) combinatorial algorithm with 1 + multiplicative error cannot have an additive error less than 2 − , unless we make a major breakthrough for Boolean matrix multiplication [19] and many other long-standing problems [39]. The algorithm can also be turned into a (2 + )-approximation algorithm (without an In Proc. FOCS
File Format	PDF
Language	English
Publisher Date	2013-01-01
Access Restriction	Open
Content Type	Text
Resource Type	Article