Research output: Contribution to conference types › Paper

Panagiotis Charalampopoulos, Shay Mozes, Benjamin Tebeka

Original language | English |
---|---|

Pages | 2110-2123 |

Number of pages | 14 |

Publication status | Published - 1 Jan 2019 |

Event | 30th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019 - San Diego, United States Duration: 6 Jan 2019 → 9 Jan 2019 |

Conference | 30th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019 |
---|---|

Country | United States |

City | San Diego |

Period | 6/01/2019 → 9/01/2019 |

We consider exact distance oracles for directed weighted planar graphs in the presence of failing vertices. Given a source vertex u, a target vertex v and a set X of k failed vertices, such an oracle returns the length of a shortest u-to-v path that avoids all vertices in X. We propose oracles that can handle any number k of failures. More specifically, for a directed weighted planar graph with n vertices, any constant k, and for any q ∈ [1, n], we propose an oracle of size Õ(^{n}_{q}^{k}_{2}^{+3}_{k}_{+1}^{/}^{2} ) that answers queries in Õ(q) time.^{1} In particular, we show an Õ(n)-size, Õ(n)-query-time oracle for any constant k. This matches, up to polylogarithmic factors, the fastest failure-free distance oracles with nearly linear space. For single vertex failures (k = 1), our Õ(^{n}_{q}^{5}_{3}^{/}^{2} )-size, Õ(q)query-time oracle improves over the previously best known tradeoff of Baswana et al. [SODA 2012] by polynomial factors for q = Ω(n^{t}), t ∈ (1/4, 1/2]. For multiple failures, no planarity exploiting results were previously known.

King's College London - Homepage

© 2018 King's College London | Strand | London WC2R 2LS | England | United Kingdom | Tel +44 (0)20 7836 5454