{"ID":2896515,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2507.06721","arxiv_id":"2507.06721","title":"Faster Algorithms for $(2k-1)$-Stretch Distance Oracles","abstract":"Let $G=(V, E)$ be an undirected $n$-vertices $m$-edges graph with non-negative edge weights. In this paper, we present three new algorithms for constructing a $(2k-1)$-stretch distance oracle with $O(n^{1+\\frac{1}{k}})$ space. The first algorithm runs in $\\Ot(\\max(n^{1+2/k}, m^{1-\\frac{1}{k-1}}n^{\\frac{2}{k-1}}))$ time, and improves upon the $\\Ot(\\min(mn^{\\frac{1}{k}},n^2))$ time of Thorup and Zwick [STOC 2001, JACM 2005] and Baswana and Kavitha [FOCS 2006, SICOMP 2010], for every $k \u003e 2$ and $m=Ω(n^{1+\\frac{1}{k}+\\eps})$. This yields the first truly subquadratic time construction for every $2 \u003c k \u003c 6$, and nearly resolves the open problem posed by Wulff-Nilsen [SODA 2012] on the existence of such constructions. The two other algorithms have a running time of the form $\\Ot(m+n^{1+f(k)})$, which is near linear in $m$ if $m=Ω(n^{1+f(k)})$, and therefore optimal in such graphs. One algorithm runs in $\\Ot(m+n^{\\frac32+\\frac{3}{4k-6}})$-time, which improves upon the $\\Ot(n^2)$-time algorithm of Baswana and Kavitha [FOCS 2006, SICOMP 2010], for $3 \u003c k \u003c 6$, and upon the $\\Ot(m+n^{\\frac{3}{2}+\\frac{2}{k}+O(k^{-2})})$-time algorithm of Wulff-Nilsen [SODA 2012], for every $k\\geq 6$. This is the first linear time algorithm for constructing a $7$-stretch distance oracle and a $9$-stretch distance oracle, for graphs with truly subquadratic density.\\footnote{with $m=n^{2-\\eps}$ for some $\\eps \u003e 0$.} The other algorithm runs in $\\Ot(\\sqrt{k}m+kn^{1+\\frac{2\\sqrt{2}}{\\sqrt{k}}})$ time, (and hence relevant only for $k\\ge 16$), and improves upon the $\\Ot(\\sqrt{k}m+kn^{1+\\frac{2\\sqrt{6}}{\\sqrt{k}}+O(k^{-1})})$ time algorithm of Wulff-Nilsen [SODA 2012] (which is relevant only for $k\\ge 96$). ...","short_abstract":"Let $G=(V, E)$ be an undirected $n$-vertices $m$-edges graph with non-negative edge weights. In this paper, we present three new algorithms for constructing a $(2k-1)$-stretch distance oracle with $O(n^{1+\\frac{1}{k}})$ space. The first algorithm runs in $\\Ot(\\max(n^{1+2/k}, m^{1-\\frac{1}{k-1}}n^{\\frac{2}{k-1}}))$ time...","url_abs":"https://arxiv.org/abs/2507.06721","url_pdf":"https://arxiv.org/pdf/2507.06721v2","authors":"[\"Avi Kadria\",\"Liam Roditty\"]","published":"2025-07-09T10:22:48Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}