Exact distance oracles for planar graphs with failing vertices

TY - CONF

T1 - Exact distance oracles for planar graphs with failing vertices

AU - Charalampopoulos, Panagiotis

AU - Mozes, Shay

AU - Tebeka, Benjamin

PY - 2019/1/1

Y1 - 2019/1/1

N2 - 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 Õ(nqk2+3k+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 Õ(nq53/2 )-size, Õ(q)query-time oracle improves over the previously best known tradeoff of Baswana et al. [SODA 2012] by polynomial factors for q = Ω(nt), t ∈ (1/4, 1/2]. For multiple failures, no planarity exploiting results were previously known.

AB - 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 Õ(nqk2+3k+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 Õ(nq53/2 )-size, Õ(q)query-time oracle improves over the previously best known tradeoff of Baswana et al. [SODA 2012] by polynomial factors for q = Ω(nt), t ∈ (1/4, 1/2]. For multiple failures, no planarity exploiting results were previously known.

UR - http://www.scopus.com/inward/record.url?scp=85066954197&partnerID=8YFLogxK

M3 - Paper

AN - SCOPUS:85066954197

SP - 2110

EP - 2123

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

Y2 - 6 January 2019 through 9 January 2019

ER -