Alladi Ramakrishnan Hall

Fast 2-approximation algorithm for unweighted All Pair Shortest Path.

Pritesh Kumar

IMSc

Given a graph G =(V,E), in
this problem, the goal is to compute the distances between all pairs
of vertices in a graph. In this talk, we will see a recent fast
approximation algorithm for APSP.

This talk is essentially a presentation of the findings discussed in
the following paper, which is set to appear in the proceedings of
SODA24:
Title: Fast 2-Approximate All-Pairs Shortest Paths
Authors: Michal Dory, Sebastian Forster, Yael Kirkpatrick, Yasamin
Nazari, Virginia Vassilevska Williams, and Tijn de Vos.
Link to the Paper: arxiv.org/abs/2307.09258