2016/05/15 by Michael Elkin, Ofer Neiman, Elkin, Michael +1 · 4 citations
Computer Science · Mathematics · #Complexity and Algorithms in Graphs #Advanced Graph Theory Research #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.1605.04538
A (\β,\ε)-hopset for a weighted undirected n-vertex graph\nG=(V,E) is a set of edges, whose addition to the graph guarantees that every\npair of vertices has a path between them that contains at most \β edges,\nwhose length is within 1+\ε of the shortest path. In her seminal paper,\nCohen cite[JACM 2000]C00 introduced the notion of hopsets in the context of\nparallel computation of approximate shortest paths, and since then it has found\nnumerous applications in various other settings, such as dynamic graph\nalgorithms, distributed computing, and the streaming model.\n Cohen citeC00 devised efficient algorithms for constructing hopsets with\n em polylogarithmic in n number of hops. Her constructions remain the\nstate-of-the--art since the publication of her paper in STOC'94, i.e., for more\nthan two decades.\n In this paper we exhibit the first construction of sparse hopsets with a em\nconstant number of hops. We also find efficient algorithms for hopsets in\nvarious computational settings, improving the best known constructions.\nGenerally, our hopsets strictly outperform the hopsets of citeC00, both in\nterms of their parameters, and in terms of the resources required to construct\nthem.\n We demonstrate the applicability of our results for the fundamental problem\nof computing approximate shortest paths from s sources. Our results improve\nthe running time for this problem in the parallel, distributed and streaming\nmodels, for a vast range of s.\n