Buchumschlag

Negative-Weight Single-Source Shortest Paths in Near-linear Time

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Bernstein, Aaron, Nanongkai, Danupon, Wulff-Nilsen, Christian
Format:	Preprint
Veröffentlicht:	2022
Schlagworte:	Data Structures and Algorithms
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

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

Fully Dynamic Exact Edge Connectivity in Sublinear Time
von: Goranci, Gramoz, et al.
Veröffentlicht: (2023)

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

Minimum $s$--$t$ Cuts with Fewer Cut Queries
von: Jiang, Yonggang, et al.
Veröffentlicht: (2025)

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

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

Deterministic Negative-Weight Shortest Paths in Nearly Linear Time via Path Covers
von: Haeupler, Bernhard, et al.
Veröffentlicht: (2025)

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

Shortcuts and Transitive-Closure Spanners Approximation
von: Chalermsook, Parinya, et al.
Veröffentlicht: (2025)

Shortcutting for Negative-Weight Shortest Path
von: Li, George Z., et al.
Veröffentlicht: (2025)

Faster Approximation Algorithms for Restricted Shortest Paths in Directed Graphs
von: Ashvinkumar, Vikrant, et al.
Veröffentlicht: (2024)

Deterministic Padded Decompositions and Negative-Weight Shortest Paths
von: Li, Jason
Veröffentlicht: (2025)

Uniform Sampling of Negative Edge Weights in Shortest Path Networks
von: Geis, Lukas, et al.
Veröffentlicht: (2024)

Single-Source Shortest Path Problem in Weighted Disk Graphs
von: An, Shinwoo, et al.
Veröffentlicht: (2025)

Faster Negative-Weight Shortest Paths and Directed Low-Diameter Decompositions
von: Li, Jason, et al.
Veröffentlicht: (2025)

Sublinear Data Structures for Nearest Neighbor in Ultra High Dimensions
von: Herold, Martin G., et al.
Veröffentlicht: (2025)

Lossless Derandomization for Undirected Single-Source Shortest Paths and Approximate Distance Oracles
von: Yan, Shuyi
Veröffentlicht: (2025)

Lower Bounds for Adaptive Relaxation-Based Algorithms for Single-Source Shortest Paths
von: Atalig, Sunny, et al.
Veröffentlicht: (2024)

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

Incremental Approximate Single-Source Shortest Paths with Predictions
von: McCauley, Samuel, et al.
Veröffentlicht: (2025)

Verifying Shortest Paths in Linear Time
von: Shokry, Ahmed, et al.
Veröffentlicht: (2024)

Better Bounds for Semi-Streaming Single-Source Shortest Paths
von: Assadi, Sepehr, et al.
Veröffentlicht: (2025)

All-Pairs Shortest Paths with Few Weights per Node
von: Abboud, Amir, et al.
Veröffentlicht: (2025)

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

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

The Discrepancy of Shortest Paths
von: Bodwin, Greg, et al.
Veröffentlicht: (2024)

From Unweighted to Weighted Dynamic Matching in Non-Bipartite Graphs: A Low-Loss Reduction
von: Bernstein, Aaron, et al.
Veröffentlicht: (2025)

Maximum Flow by Augmenting Paths in $n^{2+o(1)}$ Time
von: Bernstein, Aaron, et al.
Veröffentlicht: (2024)

A Faster Directed Single-Source Shortest Path Algorithm
von: Duan, Ran, et al.
Veröffentlicht: (2026)

Breaking the Sorting Barrier for Directed Single-Source Shortest Paths
von: Duan, Ran, et al.
Veröffentlicht: (2025)

On Constrained and k Shortest Paths
von: Bendahi, Abderrahim, et al.
Veröffentlicht: (2024)

Shortest Paths in Multimode Graphs
von: Kirkpatrick, Yael, et al.
Veröffentlicht: (2025)

All-Hops Shortest Paths
von: Williams, Virginia Vassilevska, et al.
Veröffentlicht: (2024)

Enhanced Methods for the Weight Constrained Shortest Path Problem
von: Ahmadi, Saman, et al.
Veröffentlicht: (2022)

The Steiner Shortest Path Tree Problem
von: Asher, Omer, et al.
Veröffentlicht: (2025)

Hierarchical Multicriteria Shortest Path Search
von: Kurbanov, Temirlan, et al.
Veröffentlicht: (2025)

Covering Approximate Shortest Paths with DAGs
von: Assadi, Sepehr, et al.
Veröffentlicht: (2025)

Generalized Flow in Nearly-linear Time on Moderately Dense Graphs
von: Jiang, Shunhua, et al.
Veröffentlicht: (2025)

An Improved Algorithm for Shortest Paths in Weighted Unit-Disk Graphs
von: Brewer, Bruce W., et al.
Veröffentlicht: (2024)

Fully Dynamic Shortest Paths in Sparse Digraphs
von: Karczmarz, Adam, et al.
Veröffentlicht: (2024)