Deterministic Combinatorial Replacement Paths and Distance Sensitivity Oracles

DOI10.4230/LIPIcs.ICALP.2019.12OpenAlexW2945847545MaRDI QIDQ5091160

Noga Alon, Sarel Cohen, Shiri Chechik

Publication date: 21 July 2022

Full work available at URL: https://arxiv.org/abs/1905.07483

zbMATH Keywords

derandomizationreplacement pathsdistance sensitivity oracles

Mathematics Subject Classification ID

Theory of computing (68Qxx) Theory of software (68Nxx)

Related Items (2)

Compact distance oracles with large sensitivity and low stretch ⋮ Incremental distance products via faulty shortest paths

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• \(f\)-sensitivity distance oracles and routing schemes
• Improved algorithms for the \(k\) simple shortest paths and the replacement paths problems
• The k most vital arcs in the shortest path problem
• A faster computation of the most vital edge of a shortest path
• Replacement Paths and Distance Sensitivity Oracles via Fast Matrix Multiplication
• Approximate Shortest Paths Avoiding a Failed Vertex: Optimal Size Data Structures for Unweighted Graphs
• Replacement paths and k simple shortest paths in unweighted directed graphs
• Oracles for Distances Avoiding a Failed Node or Link
• Finding the k Shortest Paths
• Replacement Paths via Row Minima of Concise Matrices
• A nearly optimal oracle for avoiding failed vertices and edges
• A Deterministic Distributed Algorithm for Exact Weighted All-Pairs Shortest Paths in Õ(n 3/2 ) Rounds
• Graph expansion and communication costs of fast matrix multiplication
• Finding the K Shortest Loopless Paths in a Network
• A Procedure for Computing the K Best Solutions to Discrete Optimization Problems and Its Application to the Shortest Path Problem

This page was built for publication: Deterministic Combinatorial Replacement Paths and Distance Sensitivity Oracles