A (β, )-hopset är informellt en viktad kantuppsättning som, när den läggs till i en graf, gör det möjligt att komma från punkt a till punkt b med hjälp av en väg med högst β-kanter ("hopp") och längd (1 + ) dist(a, b). I detta papper observerar vi att Thorup och Zwick sublinjära additive emulatorer är också faktiskt (O(k/ ) k, )-hopset för varje > 0, och att med en liten förändring till Thorup-Zwick konstruktion, storleken på humlesetet kan göras O(n 1 + 1 2 k+1 −1 ). Som corollaries rakar vi också "k" faktorer av storleken på Thorup och Zwicks [20] sublinjära additive emulatorer och de glesaste kända (1 +, O (k/ ) k-1)-spanners, på grund av Abboud, Bodwin, och Pettie [1].
Specifikt, Ref-konstruktion (β, )-hopp av storlek O(n 1+ 1 2 k+1 −1 ) med β = O(k/ ) k, där de senaste existentiella resultaten visar att
Thorup–Zwick emulators are universally optimal hopsets
{'venue': 'Information Processing Letters', 'journal': 'Information Processing Letters', 'mag_field_of_study': ['Mathematics', 'Computer Science']}