Tata Institute of Fundamental Research
Fault-Tolerant Reachability and Strong-connectivity Structures
STCS Seminar
Speaker:
Keerti Choudhary (Weizmann Institute of Science, Israel)
Organiser:
Ramprasad Saptharishi
Date:
Thursday, 3 Oct 2019, 11:30 to 12:30
Venue:
A-201 (STCS Seminar Room)
(Scan to add to calendar)
Abstract:
Abstract: Reachability and strong-connectivity are some of the fundamental graph problems. In the static setting, both problems 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, min-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. How fast can we compute the strongly connected components, again on the occurrence of failures?
3. Does there exist a sparse certificate for these structures that remains valid even after a bounded number of failures?
The solutions to these problems employ extremely basic tools like max-flows, min-cuts, and heavy-path-decomposition.
| Speaker: | Keerti Choudhary (Weizmann Institute of Science, Israel) |
| Organiser: | Ramprasad Saptharishi |
| Date: | Thursday, 3 Oct 2019, 11:30 to 12:30 |
| Venue: | A-201 (STCS Seminar Room) |
(Scan to add to calendar)
Abstract:
Abstract: Reachability and strong-connectivity are some of the fundamental graph problems. In the static setting, both problems 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, min-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. How fast can we compute the strongly connected components, again on the occurrence of failures?
3. Does there exist a sparse certificate for these structures that remains valid even after a bounded number of failures?
The solutions to these problems employ extremely basic tools like max-flows, min-cuts, and heavy-path-decomposition.
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. How fast can we compute the strongly connected components, again on the occurrence of failures?
3. Does there exist a sparse certificate for these structures that remains valid even after a bounded number of failures?
The solutions to these problems employ extremely basic tools like max-flows, min-cuts, and heavy-path-decomposition.