Near optimal algorithm for the directed single source replacement paths problem
From MaRDI portal
Cites work
- A faster computation of the most vital edge of a shortest path
- Algorithmic mechanism design (extended abstract)
- All pairs shortest paths using bridging sets and rectangular matrix multiplication
- An algorithm for finding all shortest paths using \(N^{2\cdot 81}\) infinite-precision multiplications
- Faster replacement paths
- Finding the Hidden Path: Time Bounds for All-Pairs Shortest Paths
- Finding the k Shortest Paths
- Finding the most vital node of a shortest path.
- scientific article; zbMATH DE number 5764782 (Why is no real title available?)
- Improved distance sensitivity oracles via fast single-source replacement paths
- Multiplying matrices faster than coppersmith-winograd
- Near optimal algorithms for the single source replacement paths problem
- On the difficulty of some shortest path problems
- On the exponent of all pairs shortest path problem
- Powers of tensors and fast matrix multiplication
- Replacement paths and k simple shortest paths in unweighted directed graphs
- Shortest paths in directed planar graphs with negative lengths: a linear-space \(O(n\log^{2} n)\)-time algorithm
- Solving the replacement paths problem for planar directed graphs in O(n n) time
- Subcubic equivalences between path, matrix, and triangle problems
- The k most vital arcs in the shortest path problem
Cited in
(5)- Near optimal algorithm for fault tolerant distance oracle and single source replacement path problem
- Fault tolerant max-cut
- Faster monotone min-plus product, range mode, and single source replacement paths
- A nearly linear time construction of approximate single-source distance sensitivity oracles
- Undirected 3-fault replacement path in nearly cubic time
This page was built for publication: Near optimal algorithm for the directed single source replacement paths problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6842491)
