{"ID":2886003,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2508.04872","arxiv_id":"2508.04872","title":"A Refutation of Elmasry's $\\tilde{O}(m \\sqrt{n})$-Time Algorithm for Single-Source Shortest Paths","abstract":"In this note we examine the recent paper \"Breaking the Bellman-Ford Shortest-Path Bound\" by Amr Elmasry, where he presents an algorithm for the single-source shortest path problem and claims that its running time complexity is $\\tilde{O}(m\\sqrt{n})$, where $n$ is the number of vertices and $m$ is the number of edges. We show that his analysis is incorrect, by providing an example of a weighted graph on which the running time of his algorithm is $Ω(mn)$.","short_abstract":"In this note we examine the recent paper \"Breaking the Bellman-Ford Shortest-Path Bound\" by Amr Elmasry, where he presents an algorithm for the single-source shortest path problem and claims that its running time complexity is $\\tilde{O}(m\\sqrt{n})$, where $n$ is the number of vertices and $m$ is the number of edges. W...","url_abs":"https://arxiv.org/abs/2508.04872","url_pdf":"https://arxiv.org/pdf/2508.04872v1","authors":"[\"Sunny Atalig\",\"Marek Chrobak\"]","published":"2025-08-06T20:51:13Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[\"Large Language Model\"]","has_code":false}