We will research variants of shortest paths algorithms and data-structures in setting with failures as well as fixed-parameter tractable algorithms in settings with failures, as described below.
(1) Fault-tolerant shortest paths - We study variants of shortest paths algorithms and data-structures in setting with failures. In particular, we study the Replacement Paths (RP) problem, where given a shortest s-t-path P in a graph, we want to compute for every edge e in P the shortest path from s to t avoiding e. The goal of this research direction is to construct efficient algorithm and data-structures for computing both exact and approximate replacement paths in various settings, and derandomize existing randomized algorithms for these problems.
(2) Faulttolerant fixed-parameter tractable algorithms – We aim to develop efficient algorithms and data-structures to solve paramterized problems (such as k-path, vertex cover, maximum independent set, etc.) in settings with failures. Upon a failure, it is inefficient to re-compute in exponential time the solution to the problem. Instead the goal is preprocess the graph in exponential time, and then upon failure to compute the solution in polynomial or even poly-logarithmic time.
(3) Benchmarking algorithms on NVRAM - Non-Volatile Random Access Memory is an up and coming hardware technology, it allows data to persist in memory even if the system crashes or looses power and also comes which much larger storing capacity (up to 6TB). New algorithms are needed to take advantage of these features. We want to find found what is possible on NVRAM machines especially in the context of large real-world networks. This research projects also involves benchmarking the algorithm implemented in GraphBLAST on actual hardware.
This list is not exhaustive and we are open to more suggestions.