Talk by Shiri Chechik, Microsoft Research

Fully Dynamic Approximate Distance Oracles for Planar Graphs via Forbidden-Set Distance Labels

16th September 2013 - at 4.00 p.m.


Distance oracle is a data structure that provides fast answers to distance queries.

Recently, the problem of designing distance oracles capable of answering restricted distance queries, that is, estimating distances on a subgraph avoiding some forbidden\faulty vertices, has attracted a lot of attention.

In this talk, we will consider forbidden set distance oracles for planar graphs. I’ll present an efficient compact distance oracle that is capable of handling any number of failures. 

In addition, we will consider a closely related notion of fully dynamic distance oracles. In the dynamic distance oracle problem instead of getting the failures in the query phase, we rather need to handle an adversarial online sequence of update and query operations.

Each query operation involves two vertices s and t whose distance needs to be estimated. Each update operation involves inserting/deleting a vertex/edge from the graph.

I’ll show that our forbidden set distance oracle can be tweaked to give fully dynamic distance oracle with improved bounds compared to the previously known fully dynamic distance oracle for planar graphs.

Joint work with Ittai Abraham and Cyril Gavoille

Scientific Host: Mikkel Thorup

Short bio:

I am a post doctoral researcher at Microsoft Research Silicon Valley. I recently completed my PhD under the supervision of Prof. David Peleg  in the  Department of Computer Science and Applied Mathematics,  at the Weizmann Institute of Science.

Research Interests

I am broadly interested in the theory of algorithms. Specific areas are:

  • • Distributed Algorithms
  • • Combinatorial Algorithms
  • • Dynamic Algorithms
  • • Networking