Talks & Seminars
Title: Fault-Tolerant Reachability and Strong-connectivity Structures
Dr. Keerti Choudhary, Weizmann Institute of Science
Date & Time: October 14, 2019 10:30
Venue: Dept. of CSE, Room no. 109, 01st Floor, New CSE/CC Bldg.
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 Profile:
Keerti Choudhary is currently a postdoc at Weizmann Institute of Science. She works in the area of Algorithms, particularly dynamic and fault-tolerant graph algorithms, Combinatorics, and Graph theory. She finished her PhD. in 2017 at IIT Kanpur. She is the recipient of the ACM India Doctoral Dissertation Award 2019 and the IBM Outstanding Ph.D. Thesis Award at IIT Kanpur for the year 2016-17.
List of Talks


Faculty CSE IT
Forgot Password
    [+] Sitemap     Feedback