| Title | : | Distributed Fault Tolerant Distance Computation in Graphs |
| Speaker | : | Vignesh Manoharan (UT Austin, USA) |
| Details | : | Fri, 19 Dec, 2025 3:00 PM @ SSB 334 |
| Abstract: | : | Routing messages is an important problem in distributed networks, and efficient fault-tolerant routing requires methods to maintain shortest distances between nodes when faults occur. In this talk, I will introduce fault-tolerant versions of shortest path problems in graphs, and discuss algorithms and lower bounds for these problems in the "CONGEST" model of bandwidth-limited distributed computation. Specifically, I will present results for the Replacement Paths problem and the Distance Sensitivity Oracle problem, both of which deal with computing shortest paths in a graph when a single edge fails. |
