Cover Image

A Simple Parallel Algorithm with Near-Linear Work for Negative-Weight Single-Source Shortest Paths

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Fischer, Nick, Haeupler, Bernhard, Latypov, Rustam, Roeyskoe, Antti, Sulser, Aurelio L.
Format:	Preprint
Published:	2024
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Near-Optimal Directed Low-Diameter Decompositions
by: Bringmann, Karl, et al.
Published: (2025)

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

Better Diameter Bounds for Efficient Shortcuts and a Structural Criterion for Constructiveness
by: Haeupler, Bernhard, et al.
Published: (2026)

Maintaining Routing Structures under Deletions via Self-Pruning
by: Haeupler, Bernhard, et al.
Published: (2025)

Parallel, Distributed, and Quantum Exact Single-Source Shortest Paths with Negative Edge Weights
by: Ashvinkumar, Vikrant, et al.
Published: (2023)

A Constant-Approximation Distance Labeling Scheme under Polynomially Many Edge Failures
by: Haeupler, Bernhard, et al.
Published: (2026)

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

Low-Step Multi-Commodity Flow Emulators
by: Haeupler, Bernhard, et al.
Published: (2024)

An $n^{2+o(1)}$ Time Algorithm for Single-Source Negative Weight Shortest Paths
by: Khanna, Sanjeev, et al.
Published: (2026)

Near-Optimal Algorithm for Directed Expander Decompositions
by: Sulser, Aurelio L., et al.
Published: (2024)

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

All-Pairs Shortest Paths with Few Weights per Node
by: Abboud, Amir, et al.
Published: (2025)

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

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

Lower Bounds for Adaptive Relaxation-Based Algorithms for Single-Source Shortest Paths
by: Atalig, Sunny, et al.
Published: (2024)

Single-Source Shortest Path Problem in Weighted Disk Graphs
by: An, Shinwoo, et al.
Published: (2025)

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

Parallel Reachability and Shortest Paths on Non-sparse Digraphs: Near-linear Work and Sub-square-root Depth
by: Ashvinkumar, Vikrant, et al.
Published: (2026)

Parallel $(1+ε)$-Approximate Multi-Commodity Mincost Flow in Almost Optimal Depth and Work
by: Haeupler, Bernhard, et al.
Published: (2025)

Minimizing Tardy Processing Time on a Single Machine in Near-Linear Time
by: Fischer, Nick, et al.
Published: (2024)

Implementation and Brief Experimental Analysis of the Duan et al. (2025) Algorithm for Single-Source Shortest Paths
by: Castro, Lucas, et al.
Published: (2025)

Simple Length-Constrained Expander Decompositions
by: Bodwin, Greg, et al.
Published: (2025)

A Faster Directed Single-Source Shortest Path Algorithm
by: Duan, Ran, et al.
Published: (2026)

Verifying Shortest Paths in Linear Time
by: Shokry, Ahmed, et al.
Published: (2024)

A Refutation of Elmasry's $\tilde{O}(m \sqrt{n})$-Time Algorithm for Single-Source Shortest Paths
by: Atalig, Sunny, et al.
Published: (2025)

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

New Structures and Algorithms for Length-Constrained Expander Decompositions
by: Haeupler, Bernhard, et al.
Published: (2024)

Adaptive Massively Parallel Coloring in Sparse Graphs
by: Latypov, Rustam, et al.
Published: (2024)

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

Maintaining Random Assignments under Adversarial Dynamics
by: Haeupler, Bernhard, et al.
Published: (2026)

Incremental Approximate Single-Source Shortest Paths with Predictions
by: McCauley, Samuel, et al.
Published: (2025)

A Simple Algorithm for Trimmed Multipoint Evaluation
by: Fischer, Nick, et al.
Published: (2025)

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

A Polynomial-Time Algorithm for the Next-to-Shortest Path Problem on Positively Weighted Directed Graphs
by: Chen, Kuowen, et al.
Published: (2025)

An Improved Algorithm for Shortest Paths in Weighted Unit-Disk Graphs
by: Brewer, Bruce W., et al.
Published: (2024)

Massively Parallel Algorithms for Approximate Shortest Paths
by: Dory, Michal, et al.
Published: (2024)

Better Bounds for Semi-Streaming Single-Source Shortest Paths
by: Assadi, Sepehr, et al.
Published: (2025)

Parallel Approximate Maximum Flows in Near-Linear Work and Polylogarithmic Depth
by: Agarwal, Arpit, et al.
Published: (2024)

Parallel Small Vertex Connectivity in Near-Linear Work and Polylogarithmic Depth
by: Jiang, Yonggang, et al.
Published: (2025)

Faster Approximation Algorithms for Restricted Shortest Paths in Directed Graphs
by: Ashvinkumar, Vikrant, et al.
Published: (2024)