First Near-Additive All-Pairs Approximate Shortest Paths in Decremental Weighted Graphs
cs.DS
Submitted: 2026-11-03
Updated: 2026-11-03
Terminology
Sources
- Approximating APSP without Scaling: Equivalence of Approximate Min-Plus and Exact Min-Max
- Fast 2-Approximate All-Pairs Shortest Paths
- New Tradeoffs for Decremental Approximate All-Pairs Shortest Paths
- Almost Shortest Paths with Near-Additive Error in Weighted Graphs
- Decremental Single-Source Shortest Paths on Undirected Graphs in Near-Linear Total Update Time
- Improved Additive Approximation Algorithms for APSP
- New weighted additive spanners
- Near-Optimal Decremental Hopsets with Applications
- Weighted Emulators with Local Heaviest Edges Stretch for Undirected Graphs
- Greedy Completion for Weighted $(\alpha,\beta)$-Spanners
Related papers
- Exploiting Low Scanwidth to Resolve Soft Polytomies
- PHastR: Faster Minimal Perfect Hashing with Rotated Layouts
- Fine-Grained Complexity of Approximating Vector Knapsack: A Faster Algorithm and Equivalence with k-SUM in 2D
- Polynomial-time computation of p-contraction fixed points for even p
- Separations Between Submodular-Like Graph Widths
- Bounded Integer Programming in Almost N 2d Time