For a positive parameter β, the β-bounded distance between a pair of vertices u, v in a weighted undirected graph G = (V, E, ω) is the length of the shortest u − v path in G with at most β edges, aka hops. For β as above and Hopsets are a fundamental graph-theoretic and graph-algorithmic construct, and they are widely used for distance-related problems in a variety of computational settings. Currently existing constructions of hopsets produce hopsets either with Ω(n log n) edges, or with a hopbound n Ω(1) . In this paper we devise a construction of linear-size hopsets with hopbound (ignoring the dependence on ǫ) (log n) This improves the previous bound almost exponentially. We also devise efficient implementations of our construction in PRAM and distributed settings. The only existing PRAM algorithm [EN16a] for computing hopsets with a constant (i.e., independent of n) hopbound requires n Ω(1) time. We devise a PRAM algorithm with polylogarithmic running time for computing hopsets with a constant hopbound, i.e., our running time is exponentially better than the previous one. Moreover, these hopsets are also significantly sparser than their counterparts from [EN16a] . We use our hopsets to devise a distributed routing scheme that exhibits near-optimal tradeoff between individual memory requirementÕ(n 1/k ) of vertices throughout preprocessing and routing phases of the algorithm, and stretch O(k), along with a near-optimal construction time ≈ D + n 1/2+1/k , where D is the hop-diameter of the input graph. Previous distributed routing algorithms either suffered from a prohibitively large memory requirement Ω( √ n), or had a near-linear construction time, even on graphs with small hop-diameter D.
Elkin and Neiman REF claim a fully compact distributed routing algorithm using low memory in both the preprocessing and routing phases.
Linear-Size Hopsets with Small Hopbound, and Distributed Routing with Low Memory
ArXiv
ArXiv
Mathematics Computer Science