Cover Image

Additive, Near-Additive, and Multiplicative Approximations for APSP in Weighted Undirected Graphs: Trade-offs and Algorithms

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Roditty, Liam, Sapir, Ariel
Format:	Preprint
Published:	2025
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Weighted Emulators with Local Heaviest Edges Stretch for Undirected Graphs
by: Roditty, Liam, et al.
Published: (2026)

Improved Additive Approximation Algorithms for APSP
by: Jin, Ce, et al.
Published: (2025)

On the Space Usage of Approximate Distance Oracles with Sub-2 Stretch
by: Kopelowitz, Tsvi, et al.
Published: (2023)

Faster Algorithms for $(2k-1)$-Stretch Distance Oracles
by: Kadria, Avi, et al.
Published: (2025)

New approximate distance oracles and their applications
by: Kadria, Avi, et al.
Published: (2025)

New algorithms for girth and cycle detection
by: Roditty, Liam, et al.
Published: (2025)

New Diameter Approximations via Distance Oracle Techniques
by: Kirkpatrick, Yael, et al.
Published: (2026)

Faster Weighted and Unweighted Tree Edit Distance and APSP Equivalence
by: Nogler, Jakob, et al.
Published: (2024)

Message Optimality and Message-Time Trade-offs for APSP and Beyond
by: Dufoulon, Fabien, et al.
Published: (2025)

Anarchy in the APSP: Algorithm and Hardness for Incorrect Implementation of Floyd-Warshall
by: Koo, Jaehyun
Published: (2024)

Sandpile Prediction on Undirected Graphs
by: Chang, Ruinian, et al.
Published: (2023)

Bootstrapping Dynamic APSP via Sparsification
by: Kyng, Rasmus, et al.
Published: (2024)

Lightweight Near-Additive Spanners
by: Gitlitz, Yuval, et al.
Published: (2024)

Additive Approximation Schemes for Low-Dimensional Embeddings
by: Anderson, Prashanti, et al.
Published: (2025)

A Simple Dynamic Spanner via APSP
by: Kyng, Rasmus, et al.
Published: (2024)

Undirected 3-Fault Replacement Path in Nearly Cubic Time
by: Chi, Shucheng, et al.
Published: (2024)

Network Design on Undirected Series-Parallel Graphs
by: Bansal, Ishan, et al.
Published: (2024)

Personalized PageRank Estimation in Undirected Graphs
by: Bertram, Christian, et al.
Published: (2026)

Near-Tight Approximation Algorithms for Bottleneck Multiple Knapsack Problems
by: Chen, Lin, et al.
Published: (2026)

Multiplicative Auction Algorithm for Approximate Maximum Weight Bipartite Matching
by: Zheng, Da Wei, et al.
Published: (2023)

Universe Reduction for APSP: Equivalence of Three Fine-Grained Hypotheses
by: Fischer, Nick
Published: (2026)

Improved girth approximation in weighted undirected graphs
by: Kadria, Avi, et al.
Published: (2025)

Lossless Derandomization for Undirected Single-Source Shortest Paths and Approximate Distance Oracles
by: Yan, Shuyi
Published: (2025)

Directed and Undirected Vertex Connectivity Problems are Equivalent for Dense Graphs
by: Fischer, Olivier, et al.
Published: (2025)

Revisiting Local PageRank Estimation on Undirected Graphs: Simple and Optimal
by: Wang, Hanzhi
Published: (2024)

Additive Spanner Lower Bounds with Optimal Inner Graph Structure
by: Bodwin, Greg, et al.
Published: (2024)

Dynamic Connectivity in Disk Graphs
by: Baumann, Alexander, et al.
Published: (2021)

A Note on Approximating Weighted Nash Social Welfare with Additive Valuations
by: Feng, Yuda, et al.
Published: (2024)

Additive One Approximation for Minimum Degree Spanning Tree: Breaking the $O(mn)$ Time Barrier
by: Bhattacharya, Sayan, et al.
Published: (2026)

Connectivity Labeling in Faulty Colored Graphs
by: Petruschka, Asaf, et al.
Published: (2024)

Improved Sublinear Algorithms for Classical and Quantum Graph Coloring
by: Ferber, Asaf, et al.
Published: (2025)

Simple Linear-Size Additive Emulators
by: Hoppenworth, Gary
Published: (2023)

Almost-Optimal Sublinear Additive Spanners
by: Tan, Zihan, et al.
Published: (2023)

An Additive Approximation Scheme for Generating Dyadic Codings for the Outputs of an LLM
by: Bar-Lev, Daniella, et al.
Published: (2026)

An Improved Approximation Algorithm for Maximum Weight 3-Path Packing
by: Zhao, Jingyang, et al.
Published: (2025)

Improved Approximation Algorithms for Chromatic and Pseudometric-Weighted Correlation Clustering
by: Fan, Chenglin, et al.
Published: (2025)

Sampling with a Black Box: Faster Parameterized Approximation Algorithms for Vertex Deletion Problems
by: Esmer, Barış Can, et al.
Published: (2024)

A Near-Optimal Low-Energy Deterministic Distributed SSSP with Ramifications on Congestion and APSP
by: Ghaffari, Mohsen, et al.
Published: (2024)

Deterministic Near-Linear Time Minimum Cut in Weighted Graphs
by: Henzinger, Monika, et al.
Published: (2024)

Lawler-Moore Speedups via Additive Combinatorics
by: Bringmann, Karl, et al.
Published: (2026)