| Title | : | Fault-Tolerant Reachability |
| Speaker | : | Keerti Choudhary (Tel Aviv University) |
| Details | : | Mon, 27 Jan, 2020 2:00 PM @ AM Turing Hall |
| Abstract: | : | Reachability is one of the fundamental graph problems. In the static setting, the problem can be solved in O(m+n) time for any directed graph G with n vertices and m edges. However, most real-world networks are prone to failures. The failures are transient and occur for a small duration of time. Under such a setting, we would like to preprocess the graph to compute data-structures that can achieve robustness by being functional even after the occurrence of failures. In recent years, researchers have studied various questions pertaining to connectivity, distances, routing, cuts, etc. in the domain of fault tolerance networks. In this talk, I will discuss the following questions: 1. Can we compute a reachability tree in just linear time, after the occurrence of a small number of failures? 2. Does there exist a sparse certificate for reachability that remains valid even after a bounded number of failures? The solution to these problem involves simple algorithmic tools like max-flow and min-cut. |
