The Taub Faculty of Computer Science Events and Talks

The All-Pairs Shortest Paths (APSP) problem is one of the most fundamental problems in graph algorithms. It is well-known that APSP can be solved in O(n^3) time in weighted graphs, and in O(n^{omega}) time in unweighted graphs, where omega<2.376 is the exponent of matrix multiplication. However, these complexities may be high for large graphs, and it is desirable to find faster algorithms. One approach for obtaining faster algorithms is to compute approximations for APSP, rather than computing the distances exactly. In this talk, I will give an overview of algorithms for approximate APSP, and discuss recent progress and interesting open questions in this area. The talk will overview some classic results based on [Aingworth, Chekuri, Indyk, and Motwani, 1999] and [Dor, Halperin and Zwick, 2000] as well as recent results based on a joint work with Sebastian Forster, Yasamin Nazari and Tijn de Vos.