Replacement Paths and Distance Sensitivity Oracles via Fast Matrix Multiplication

DOI10.1145/2438645.2438646zbMath1301.68208OpenAlexW1963633992MaRDI QIDQ2933644

Oren Weimann, Raphael Yuster

Publication date: 5 December 2014

Published in: ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/2438645.2438646

zbMATH Keywords

fault toleranceshortest pathsdistance oraclesreplacement paths

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85) Data structures (68P05) Randomized algorithms (68W20)

Related Items (10)

Invited talk: Resilient distributed algorithms ⋮ Subcubic Equivalences between Graph Centrality Problems, APSP, and Diameter ⋮ Vertex fault tolerant additive spanners ⋮ Compact distance oracles with large sensitivity and low stretch ⋮ An efficient strongly connected components algorithm in the fault tolerant model ⋮ Improved Distance Sensitivity Oracles with Subcubic Preprocessing Time. ⋮ Improved distance sensitivity oracles with subcubic preprocessing time ⋮ Deterministic Combinatorial Replacement Paths and Distance Sensitivity Oracles ⋮ Incremental distance products via faulty shortest paths ⋮ Sparse Weight Tolerant Subgraph for Single Source Shortest Path

This page was built for publication: Replacement Paths and Distance Sensitivity Oracles via Fast Matrix Multiplication