Replacement paths and distance sensitivity oracles via fast matrix multiplication

DOI10.1145/2438645.2438646zbMATH Open1301.68208OpenAlexW1963633992MaRDI QIDQ2933644FDOQ2933644

Authors: 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

Recommendations

• Faster replacement paths and distance sensitivity oracles
• A nearly optimal oracle for avoiding failed vertices and edges
• Faster replacement paths
• Distance sensitivity oracles with subcubic preprocessing time and fast query time
• \((1 + \epsilon)\)-approximate \(f\)-sensitive distance oracles

zbMATH Keywords

shortest pathsfault tolerancedistance oraclesreplacement paths

Mathematics Subject Classification ID

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

Cited In (19)

• Invited talk: Resilient distributed algorithms
• Approximate distance sensitivity oracles in subquadratic space
• Compact and fast sensitivity oracles for single-source distances
• \((1 + \epsilon)\)-approximate \(f\)-sensitive distance oracles
• Faster replacement paths and distance sensitivity oracles
• Near-optimal distributed computation of small vertex cuts
• Improved distance sensitivity oracles with subcubic preprocessing time
• Improved distance sensitivity oracles via tree partitioning
• Deterministic replacement path covering
• Compact distance oracles with large sensitivity and low stretch
• Subcubic Equivalences between Graph Centrality Problems, APSP, and Diameter
• Improved Distance Sensitivity Oracles with Subcubic Preprocessing Time.
• Deterministic Combinatorial Replacement Paths and Distance Sensitivity Oracles
• Sparse weight tolerant subgraph for single source shortest path
• Approximate distance sensitivity oracles in subquadratic space
• Incremental distance products via faulty shortest paths
• Efficient oracles and routing schemes for replacement paths
• Distributed constructions of dual-failure fault-tolerant distance preservers
• An efficient strongly connected components algorithm in the fault tolerant model

This page was built for publication: Replacement paths and distance sensitivity oracles via fast matrix multiplication

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2933644)