Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Logo of CS4People

The Taub Faculty of Computer Science Events and Talks

Theory Seminar: Fully Dynamic Approximate Distance Oracles for Planar Graphs via Forbidden-Set Distance Labels
event speaker icon
Shiri Chechik (Weizmann Institute of Science)
event date icon
Wednesday, 09.05.2012, 12:30
event location icon
Taub 201
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 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 handing 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.