arXiv · 19 Nov 2026
Improved Bounds for Directed SSSP in Sparse and Intermediate-Density Graphs
Valery, Grishin, Aryeh Lev Zabokritskiy
Citations by database
Each database indexes a different set of journals, preprints and books, so they are shown side by side rather than blended.
- OpenCitations0
Citations per year
The current year is still counting.
- 2026 so far0
Abstract
We give a deterministic algorithm for exact single-source shortest paths (SSSP) in directed graphs with $n$ vertices, $m$ edges and nonnegative real edge weights. In the comparison-addition model, with unit-cost elementary operations on $O(\log(n+m+2))$-bit integer words, its running time for $m=O(n)$ is $O(n\sqrt{\log n}(\log\log n)^{1/4})$. For $m=Θ(n)$, this reduces the exponent of $\log\log n$ in the bound of Duan, Mao, Shu and Yin from $1/2$ to $1/4$ and removes the factor $(\log\log\log n)^{1/4}$ from the sparse bound stated in a public draft. The same algorithm improves on the bound of Duan et al. over a range of intermediate densities. At $m=Θ(n\sqrt{\log\log n})$, the running time is $O(n\sqrt{\log n}(\log\log n)^{5/8})$, reducing their exponent from $3/4$ to $5/8$. This is a consequence of a uniform bound for intermediate densities up to any fixed multiple of $n\log\log n$ edges; its validity range is larger than the range of strict improvement.
What the data shows
- No database records a citation yet, as is usual for a paper this new.
Graph
This paper in the middle, its authors and their most-cited papers below, the papers it cites to the left and the papers citing it to the right. The timeline lays every paper out by year.
Select a node for its details. Drag to pan, scroll to zoom, drag a node to move it.
Start with
Cited by 0 papers
Who cites this paper, from open citation data, with Crossref's record of each; the 100 newest when there are more.
References (0)
What it cites, from open citation data, with Crossref's record of each.