Replacement paths and distance sensitivity oracles via fast matrix multiplication

DOI10.1145/2438645.2438646MaRDI QIDQ2933644zbMATH OpenOpenAlexFDO

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

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)

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

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
• Incremental distance products via faulty shortest paths
• Efficient oracles and routing schemes for replacement paths
• Approximate distance sensitivity oracles in subquadratic space
• 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)