Subquadratic algorithm for dynamic shortest distances. Extended abstract
From MaRDI portal
Recommendations
- A subquadratic-time algorithm for decremental single-source shortest paths
- scientific article; zbMATH DE number 2149349
- Dynamic algorithms for approximating interdistances
- Sublinear time algorithms for earth mover's distance
- Subcubic cost algorithms for the all pairs shortest path problem
- Subquadratic algorithms for the diameter and the sum of pairwise distances in planar graphs
- Subquadratic algorithms for the diameter and the sum of pairwise distances in planar graphs
- An almost 2-approximation for all-pairs of shortest paths in subquadratic time
- The quadratic shortest path problem: complexity, approximability, and solution methods
- Sublinear time algorithms for metric space problems
Cited in
(10)- Maintaining shortest paths under deletions in weighted directed graphs
- A deterministic almost-tight distributed algorithm for approximating single-source shortest paths
- Single-Source Shortest Paths and Strong Connectivity in Dynamic Planar Graphs.
- Deterministic incremental APSP with polylogarithmic update time and stretch
- Fully dynamic strongly connected components in planar digraphs
- Constructing a distance sensitivity oracle in \(O(n^{2.5794}M)\) time
- Fully dynamic algorithms for transitive reduction
- Recent advances in fully dynamic graph algorithms (invited talk)
- New tradeoffs for decremental approximate all-pairs shortest paths
- Mantaining dynamic matrices for fully dynamic transitive closure
This page was built for publication: Subquadratic algorithm for dynamic shortest distances. Extended abstract
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5716965)
