Cover Image

A Refutation of Elmasry's $\tilde{O}(m \sqrt{n})$-Time Algorithm for Single-Source Shortest Paths

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Atalig, Sunny, Chrobak, Marek
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

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

Two Complexity Results on Spanning-Tree Congestion Problems
by: Atalig, Sunny, et al.
Published: (2026)

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

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

Randomized $\tilde{O}(m\sqrt{n})$ Bellman-Ford from Fineman and the Boilermakers
by: Rao, Satish
Published: (2025)

Fully dynamic biconnectivity in $\tilde{\mathcal{O}}(\log^2 n)$ time
by: Holm, Jacob, et al.
Published: (2025)

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

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

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

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

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

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

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

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

Gabow's $O(\sqrt{n}m)$ Maximum Cardinality Matching Algorithm, Revisited
by: Mehlhorn, Kurt, 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)

A 3.3904-Competitive Online Algorithm for List Update with Uniform Costs
by: Basiak, Mateusz, et al.
Published: (2025)

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

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

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

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

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

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

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

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

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

Hierarchical Multicriteria Shortest Path Search
by: Kurbanov, Temirlan, et al.
Published: (2025)

Covering Approximate Shortest Paths with DAGs
by: Assadi, Sepehr, et al.
Published: (2025)

Shortcutting for Negative-Weight Shortest Path
by: Li, George Z., 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)

Approximation Algorithms for $\ell_p$-Shortest Path and $\ell_p$-Group Steiner Tree
by: Makarychev, Yury, et al.
Published: (2024)

The Complexity of Dynamic LZ77 is $\tildeΘ(n^{2/3})$
by: Boneh, Itai, et al.
Published: (2025)

All-Pairs Minimum Cut using $\tilde{O}(n^{7/4})$ Cut Queries
by: Kenneth-Mordoch, Yotam, et al.
Published: (2025)

Faster $(Δ+ 1)$-Edge Coloring: Breaking the $m \sqrt{n}$ Time Barrier
by: Bhattacharya, Sayan, et al.
Published: (2024)

Hardness of Approximation for Shortest Path with Vector Costs
by: Carlson, Charlie, et al.
Published: (2025)

On Incremental Approximate Shortest Paths in Directed Graphs
by: Górkiewicz, Adam, et al.
Published: (2025)

Fully Dynamic Shortest Paths in Sparse Digraphs
by: Karczmarz, Adam, et al.
Published: (2024)

Parameterized Complexity of Finding Dissimilar Shortest Paths
by: Funayama, Ryo, et al.
Published: (2024)

Breaking the Bellman-Ford Shortest-Path Bound
by: Elmasry, Amr
Published: (2024)

An Optimal Algorithm for Shortest Paths in Unweighted Disk Graphs
by: Brewer, Bruce W., et al.
Published: (2025)