Copertina

An $n^{2+o(1)}$ Time Algorithm for Single-Source Negative Weight Shortest Paths

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Khanna, Sanjeev, Song, Junkai
Natura:	Preprint
Pubblicazione:	2026
Soggetti:	Data Structures and Algorithms
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

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

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

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

Maximum Bipartite Matching in $n^{2+o(1)}$ Time via a Combinatorial Algorithm
di: Chuzhoy, Julia, et al.
Pubblicazione: (2024)

An $\widetilde{O} (n^{3/7})$ Round Parallel Algorithm for Matroid Bases
di: Khanna, Sanjeev, et al.
Pubblicazione: (2026)

A Faster Deterministic Algorithm for Fully Dynamic Maximal Matching
di: Chuzhoy, Julia, et al.
Pubblicazione: (2026)

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

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

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

On the Parallel Complexity of Finding a Matroid Basis
di: Khanna, Sanjeev, et al.
Pubblicazione: (2025)

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

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

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

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

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

Optimal Parallel Basis Finding in Graphic and Related Matroids
di: Khanna, Sanjeev, et al.
Pubblicazione: (2025)

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

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

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

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

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

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

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

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

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

Fault-Tolerant Distance Oracles Below the $n \cdot f$ Barrier
di: Khanna, Sanjeev, et al.
Pubblicazione: (2026)

Sparse Navigable Graphs for Nearest Neighbor Search: Algorithms and Hardness
di: Khanna, Sanjeev, et al.
Pubblicazione: (2025)

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

Efficient Algorithms for Disjoint Shortest Paths Problem and its Extensions
di: Choudhary, Keerti, et al.
Pubblicazione: (2025)

The Discrepancy of Shortest Paths
di: Bodwin, Greg, et al.
Pubblicazione: (2024)

Correlation Clustering and (De)Sparsification: Graph Sketches Can Match Classical Algorithms
di: Assadi, Sepehr, et al.
Pubblicazione: (2025)

Near-optimal Linear Sketches and Fully-Dynamic Algorithms for Hypergraph Spectral Sparsification
di: Khanna, Sanjeev, et al.
Pubblicazione: (2025)

Breaking the Sorting Barrier for Directed Single-Source Shortest Paths
di: Duan, Ran, et al.
Pubblicazione: (2025)

Efficient Algorithms and New Characterizations for CSP Sparsification
di: Khanna, Sanjeev, et al.
Pubblicazione: (2024)

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

Shortest Paths in Multimode Graphs
di: Kirkpatrick, Yael, et al.
Pubblicazione: (2025)

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

Enhanced Methods for the Weight Constrained Shortest Path Problem
di: Ahmadi, Saman, et al.
Pubblicazione: (2022)

The Steiner Shortest Path Tree Problem
di: Asher, Omer, et al.
Pubblicazione: (2025)

Hierarchical Multicriteria Shortest Path Search
di: Kurbanov, Temirlan, et al.
Pubblicazione: (2025)