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) Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25)

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

(26)

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

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)