Fault-Tolerant Reachability and Strong-connectivity Structures by Dr. Keerti Choudhary

Location: CSA Lecture Hall (Room No. 117, Ground Floor)

Kindly note the updated details of the seminar below

Department of Computer Science and Automation
Department Seminar

Speaker : Dr Keerti Choudhary

Title : Fault-Tolerant Reachability and Strong-connectivity Structures

Date : Friday, October 18, 2019

Time : 11:00 AM

Venue : CSA Lecture Hall (Room No. 117, Ground Floor)

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.

Host Faculty : Prof. Matthew Jacob

ALL ARE WELCOME