On incremental approximate shortest paths in directed graphs
From MaRDI portal
Cites work
- A new approach to dynamic all pairs shortest paths
- Algorithms and hardness for diameter in dynamic graphs
- Amortized efficiency of a path retrieval data structure
- An On-Line Edge-Deletion Problem
- Approximating all-pair bounded-leg shortest path and APSP-AF in truly-subcubic time
- Approximating geometric bottleneck shortest paths
- Bootstrapping dynamic distance oracles
- Combining all pairs shortest paths and all pairs bottleneck paths problems
- Consequences of Faster Alignment of Sequences
- Deterministic decremental reachability, SCC, and shortest paths via directed expanders and congestion balancing
- Deterministic decremental SSSP and approximate min-cost flow in almost-linear time
- Deterministic incremental APSP with polylogarithmic update time and stretch
- Dynamic approximate shortest paths and beyond: subquadratic and worst-case update time
- Dynamic deterministic constant-approximate distance oracles with n^ worst-case update time
- Faster approximation schemes for fractional multicommodity flow problems via dynamic graph algorithms
- Faster deterministic worst-case fully dynamic all-pairs shortest paths via decremental hop-restricted shortest paths
- Fine-grained optimality of partially dynamic shortest paths and more
- Fully dynamic (2 + ε) approximate all-pairs shortest paths with fast query and close to linear update time
- Fully dynamic shortest path reporting against an adaptive adversary
- scientific article; zbMATH DE number 5764813 (Why is no real title available?)
- scientific article; zbMATH DE number 1306899 (Why is no real title available?)
- scientific article; zbMATH DE number 7788484 (Why is no real title available?)
- Improved Algorithms for Decremental Single-Source Reachability on Directed Graphs
- Incremental SSSP for sparse digraphs beyond the hopset barrier
- Maintaining shortest paths under deletions in weighted directed graphs
- Making data structures persistent
- More asymmetry yields faster matrix multiplication
- Near-optimal approximate decremental all pairs shortest paths
- Near-optimal decremental SSSP in dense weighted digraphs
- New algorithms and hardness for incremental single-source shortest paths in directed graphs
- New tradeoffs for decremental approximate all-pairs shortest paths
- On bounded leg shortest paths problems
- On dynamic shortest paths problems
- On-line computation of minimal and maximal length paths
- Popular conjectures imply strong lower bounds for dynamic problems
- Reliable Hubs for Partially-Dynamic All-Pairs Shortest Paths in Directed Graphs
- Simple label-correcting algorithms for partially dynamic approximate shortest paths in directed graphs
- Sublinear-time decremental algorithms for single-source reachability and shortest paths on directed graphs
- Tight dynamic problem lower bounds from generalized BMM and OMv
- Tight hardness for shortest cycles and paths in sparse graphs
- Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture
This page was built for publication: On incremental approximate shortest paths in directed graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7363181)
