Faster replacement paths

MaRDI QIDQ5365121zbMATH OpenFDO

Authors Virginia Vassilevska Williams

Publication date 29 September 2017

Full work available at URL https://arxiv.org/abs/1007.2216, http://dl.acm.org/citation.cfm?id=2133138

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Paths and cycles (05C38)

Recommendations

• Faster replacement paths and distance sensitivity oracles
• Automata, Languages and Programming
• A nearly optimal algorithm for approximating replacement paths and k shortest simple paths in general graphs
• Improved algorithms for the \(k\) simple shortest paths and the replacement paths problems
• On the difficulty of some shortest path problems

Cited in

(25)

• Near optimal algorithms for the single source replacement paths problem
• Automata, Languages and Programming
• Replacement paths and distance sensitivity oracles via fast matrix multiplication
• Faster replacement paths and distance sensitivity oracles
• scientific article; zbMATH DE number 1962826 (Why is no real title available?)
• Bulk-robust combinatorial optimization
• Replacement paths and k simple shortest paths in unweighted directed graphs
• A nearly optimal algorithm for approximating replacement paths and k shortest simple paths in general graphs
• STRONGER QUICKHEAPS
• Subcubic Equivalences between Graph Centrality Problems, APSP, and Diameter
• Faster replacement paths algorithms in case of edge or node failure for undirected, positive integer weighted graphs
• Improved algorithms for replacement paths problems in restricted graphs
• Near optimal algorithm for the directed single source replacement paths problem
• Simplifying and unifying replacement paths algorithms in weighted directed graphs
• Replacing Pfaffians and applications
• An experimental study on approximating k shortest simple paths
• Deterministic Combinatorial Replacement Paths and Distance Sensitivity Oracles
• Sparse weight tolerant subgraph for single source shortest path
• A nearly linear time construction of approximate single-source distance sensitivity oracles
• Faster algorithms for dual-failure replacement paths
• Faster replacement paths algorithm for undirected, positive integer weighted graphs with small diameter
• Incremental distance products via faulty shortest paths
• Conditional hardness for sensitivity problems
• Generic single edge fault tolerant exact distance oracle
• Replacement paths via row minima of concise matrices

This page was built for publication: Faster replacement paths

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