2025/07/09 by Avi Kadria, Liam Roditty, Kadria, Avi +1
#cs.DS
paper · pdf · doi:10.48550/arxiv.2507.06721
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(n1+(1)/(k)) space. The first algorithm runs in \Ot(max(n1+2/k, m1-(1)/(k-1)n(2)/(k-1))) time, and improves upon the \Ot(min(mn(1)/(k),n2)) time of Thorup and Zwick [STOC 2001, JACM 2005] and Baswana and Kavitha [FOCS 2006, SICOMP 2010], for every k > 2 and m=Ω(n1+(1)/(k)+\eps). This yields the first truly subquadratic time construction for every 2 < k < 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+n1+f(k)), which is near linear in m if m=Ω(n1+f(k)), and therefore optimal in such graphs. One algorithm runs in \Ot(m+n\frac32+(3)/(4k-6))-time, which improves upon the \Ot(n2)-time algorithm of Baswana and Kavitha [FOCS 2006, SICOMP 2010], for 3 < k < 6, and upon the \Ot(m+n^(3)/(2)+(2)/(k)+O(k-2))-time algorithm of Wulff-Nilsen [SODA 2012], for every k≥ 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.\footnotewith m=n2-\eps for some \eps > 0. The other algorithm runs in \Ot(√(k)m+kn1+(2√(2))/(√(k))) time, (and hence relevant only for k≥ 16), and improves upon the \Ot(√(k)m+kn^1+(2√(6))/(√(k))+O(k-1)) time algorithm of Wulff-Nilsen [SODA 2012] (which is relevant only for k≥ 96). ...