We present results for the distance sensitivity oracle (DSO) problem, where one needs to preprocess a given directed weighted graph \(G=(V,E)\) in order to answer queries about the shortest path distance from s to t in G that avoids edge e, for any \(s,t \in V, e \in E\) . No non-trivial results are known for DSO in the distributed CONGEST model even though it is of importance to maintain efficient communication under an edge failure. We present DSO algorithms with different tradeoffs between preprocessing and query cost – one that optimizes query response rounds, and another that prioritizes preprocessing rounds. We complement these algorithms with unconditional CONGEST lower bounds. Additionally, we present almost-optimal upper and lower bounds for the related all pairs second simple shortest path (2-APSiSP) problem.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Distributed Distance Sensitivity Oracles

  • Vignesh Manoharan,
  • Vijaya Ramachandran

摘要

We present results for the distance sensitivity oracle (DSO) problem, where one needs to preprocess a given directed weighted graph \(G=(V,E)\) in order to answer queries about the shortest path distance from s to t in G that avoids edge e, for any \(s,t \in V, e \in E\) . No non-trivial results are known for DSO in the distributed CONGEST model even though it is of importance to maintain efficient communication under an edge failure. We present DSO algorithms with different tradeoffs between preprocessing and query cost – one that optimizes query response rounds, and another that prioritizes preprocessing rounds. We complement these algorithms with unconditional CONGEST lower bounds. Additionally, we present almost-optimal upper and lower bounds for the related all pairs second simple shortest path (2-APSiSP) problem.