ICS Theory Group

ICS 269, Fall 2003: Theory Seminar

24 Oct 2003:
A new approach to dynamic all pairs shortest paths
authored by Camil Demetrescu and Giuseppe F. Italiano (STOC 2003, pp.159-166)
presented by Jonathan Sun

We study novel combinatorial properties of graphs that allow us to devise a completely new approach to dynamic all pairs shortest paths problems. Our approach yields a fully dynamic algorithm for general directed graphs with non-negative real-valued edge weights that supports any sequence of operations in O(n2poly(log n)) amortized time per update and unit worst-case time per distance query, where n is the number of vertices. We can also report shortest paths in optimal worst-case time. These bounds improve substantially over previous results and solve a long-standing open problem. Our algorithm is deterministic and uses simple data structures.