Faster replacement paths and distance sensitivity oracles

DOI10.1145/3365835MaRDI QIDQ3384662zbMATH OpenOpenAlexWikidataFDO

Authors Fabrizio Grandoni, Virginia Vassilevska Williams

Publication date 16 December 2021

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

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

zbMATH Keywords

distance sensitivity oraclesreplacement pathsshortest paths

Mathematics Subject Classification ID

Paths and cycles (05C38) Data structures (68P05) Graph theory (including graph drawing) in computer science (68R10) Nonnumerical algorithms (68W05) Analysis of algorithms (68W40)

Recommendations

• Replacement paths and distance sensitivity oracles via fast matrix multiplication
• Faster replacement paths
• A nearly optimal oracle for avoiding failed vertices and edges
• A nearly optimal algorithm for approximating replacement paths and k shortest simple paths in general graphs
• Distance sensitivity oracles with subcubic preprocessing time and fast query time

Cited in

(24)

• Improved distance sensitivity oracles with subcubic preprocessing time
• Improved distance sensitivity oracles via tree partitioning
• Improved bounds for rectangular monotone min-plus product and applications
• Replacement paths and distance sensitivity oracles via fast matrix multiplication
• Efficient oracles and routing schemes for replacement paths
• Faster replacement paths algorithms in case of edge or node failure for undirected, positive integer weighted graphs
• Conditional hardness for sensitivity problems
• Deterministic Combinatorial Replacement Paths and Distance Sensitivity Oracles
• Faster replacement paths
• Subcubic Equivalences between Graph Centrality Problems, APSP, and Diameter
• Compact distance oracles with large sensitivity and low stretch
• Deterministic Fault-Tolerant Connectivity Labeling Scheme
• Approximate distance sensitivity oracles in subquadratic space
• Approximate distance sensitivity oracles in subquadratic space
• Faster algorithms for dual-failure replacement paths
• Vital edges for (s,t)-mincut: efficient algorithms, compact structures, \& optimal sensitivity oracles
• Near optimal algorithm for fault tolerant distance oracle and single source replacement path problem
• Deterministic fault-tolerant connectivity labeling scheme
• Deterministic replacement path covering
• Faster monotone min-plus product, range mode, and single source replacement paths
• Constructing a distance sensitivity oracle in \(O(n^{2.5794}M)\) time
• Fault-tolerant ST-diameter oracles
• Undirected 3-fault replacement path in nearly cubic time
• Incremental distance products via faulty shortest paths

This page was built for publication: Faster replacement paths and distance sensitivity oracles

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