Fast constructions of lightweight spanners for general graphs Academic Article uri icon

abstract

  • It is long known that for every weighted undirected n-vertex m-edge graph G =(V, E, ω), and every integer k ⩾ 1, there exists a ((2k− 1)·(1+ ε))-spanner with O (n 1+ 1/k) edges and weight O (k· n 1/k· ω (MST (G)), for an arbitrarily small constant ε> 0.(Here ω (MST (G)) stands for the weight of the minimum spanning tree of G.) To our knowledge, the only algorithms for constructing sparse and lightweight spanners for general graphs admit high running times. Most notable in this context is the greedy algorithm of Althöfer et al.[1993], analyzed by Chandra et al.[1992], which requires O (m·(n 1+ 1/k+ n· log n)) time. In this article, we devise an efficient algorithm for constructing sparse and lightweight spanners. Specifically, our algorithm constructs ((2k− 1)·(1+ ε))-spanners with O (k· n 1+ 1/k) edges and weight O (k· n 1/k)· ω (MST (G)), where ε> 0 is an arbitrarily small …

publication date

  • June 15, 2016