Cover Image

All-Pairs Shortest Paths with Few Weights per Node

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Abboud, Amir, Fischer, Nick, Jin, Ce, Williams, Virginia Vassilevska, Xi, Zoe
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

All-Hops Shortest Paths
by: Williams, Virginia Vassilevska, et al.
Published: (2024)

Shortest Paths in Multimode Graphs
by: Kirkpatrick, Yael, et al.
Published: (2025)

Detecting Disjoint Shortest Paths in Linear Time and More
by: Akmal, Shyan, et al.
Published: (2024)

Undirected Replacement Paths: Dual Fault Reduces to Single Source
by: Nogler, Jakob, et al.
Published: (2026)

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

Beyond 2-approximation for k-Center in Graphs
by: Jin, Ce, et al.
Published: (2025)

Faster Algorithms for Text-to-Pattern Hamming Distances
by: Chan, Timothy M., et al.
Published: (2023)

Faster Combinatorial k-Clique Algorithms
by: Abboud, Amir, et al.
Published: (2024)

New Tradeoffs for Decremental Approximate All-Pairs Shortest Paths
by: Dory, Michal, et al.
Published: (2022)

Listing 6-Cycles in Sparse Graphs
by: Williams, Virginia Vassilevska, et al.
Published: (2024)

A Simple Parallel Algorithm with Near-Linear Work for Negative-Weight Single-Source Shortest Paths
by: Fischer, Nick, et al.
Published: (2024)

Fine-Grained Optimality of Partially Dynamic Shortest Paths and More
by: Saha, Barna, et al.
Published: (2024)

A Truly Subcubic Combinatorial Algorithm for Induced 4-Cycle Detection
by: Abboud, Amir, et al.
Published: (2025)

Shortcutting for Negative-Weight Shortest Path
by: Li, George Z., et al.
Published: (2025)

Fully-Dynamic All-Pairs Shortest Paths: Likely Optimal Worst-Case Update Time
by: Mao, Xiao
Published: (2023)

A Near-Optimal Offline Algorithm for Dynamic All-Pairs Shortest Paths in Planar Digraphs
by: Das, Debarati, et al.
Published: (2026)

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

Node-Weighted Triangles: Faster and Simpler
by: Akmal, Shyan, et al.
Published: (2026)

Output-sensitive approximate counting via a measure-bounded hyperedge oracle, or: How asymmetry helps estimate $k$-clique counts faster
by: Censor-Hillel, Keren, et al.
Published: (2025)

Fast Approximate Counting of Cycles
by: Censor-Hillel, Keren, et al.
Published: (2024)

New Graph Decompositions and Combinatorial Boolean Matrix Multiplication Algorithms
by: Abboud, Amir, et al.
Published: (2023)

Deterministic Padded Decompositions and Negative-Weight Shortest Paths
by: Li, Jason
Published: (2025)

New Applications of 3SUM-Counting in Fine-Grained Complexity and Pattern Matching
by: Fischer, Nick, et al.
Published: (2024)

A fast algorithm for All-Pairs-Shortest-Paths suitable for neural networks
by: Jing, Zeyu, et al.
Published: (2023)

A Refined Laser Method and Faster Matrix Multiplication
by: Alman, Josh, et al.
Published: (2020)

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

Preprocessed 3SUM for Unknown Universes with Subquadratic Space
by: Kirkpatrick, Yael, et al.
Published: (2026)

Towards Optimal Output-Sensitive Clique Listing or: Listing Cliques from Smaller Cliques
by: Dalirrooyfard, Mina, et al.
Published: (2023)

Uniform Sampling of Negative Edge Weights in Shortest Path Networks
by: Geis, Lukas, et al.
Published: (2024)

Improved All-Pairs Approximate Shortest Paths in Congested Clique
by: Bui, Hong Duc, et al.
Published: (2024)

Deterministic Negative-Weight Shortest Paths in Nearly Linear Time via Path Covers
by: Haeupler, Bernhard, et al.
Published: (2025)

Faster Negative-Weight Shortest Paths and Directed Low-Diameter Decompositions
by: Li, Jason, et al.
Published: (2025)

Negative-Weight Single-Source Shortest Paths in Near-linear Time
by: Bernstein, Aaron, et al.
Published: (2022)

The Discrepancy of Shortest Paths
by: Bodwin, Greg, et al.
Published: (2024)

A Simple, Nearly-Optimal Algorithm for Differentially Private All-Pairs Shortest Distances
by: Campbell, Jesse, et al.
Published: (2024)

On Beating $2^n$ for the Closest Vector Problem
by: Abboud, Amir, et al.
Published: (2025)

Worst-Case to Expander-Case Reductions: Derandomized and Generalized
by: Abboud, Amir, et al.
Published: (2024)

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

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

On Constrained and k Shortest Paths
by: Bendahi, Abderrahim, et al.
Published: (2024)