דלג לתוכן (מקש קיצור 's')
Logo of Technion
Logo of CS Department
אירועים

אירועים

Theory Seminar: Fully Dynamic Approximate Distance Oracles for Planar Graphs via Forbidden-Set Distance Labels
event speaker icon
שירי צ'צ'יק (מכון וייצמן למדע)
event date icon
יום רביעי, 9.5.2012, 12:30
event location icon
טאוב 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.
[בחזרה לאינדקס האירועים]