Abstract: Abstract: Failure is an unavoidable phenomenon in any network. Due to such failures, it becomes essential to find alternative shortest paths efficiently to maintain a working system. Thus, we create data structures that can answer such queries efficiently without using a great amount of memory. We will specifically explore the data structures that can answer such queries for up to two failed nodes on a path in O(log(n)) time and requiring O(n^2 log^3(n)) space.
The CICS Theory Seminar is online, free and open to the public. If you are interested in giving a talk, please email Professor Immerman or Rik Sengupta. Note that in addition to being a public lecture series, this is also a one-credit graduate seminar (CompSci 891M) that can be taken repeatedly for credit.