2021/07/30 by Hung Lê, Le, Hung, Shay Solomon +1 · 2 citations
Computer Science · Medicine · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #Drug Transport and Resistance Mechanisms #F.2.2 #FOS: Computer and information sciences
paper · pdf · doi:10.48550/arxiv.2108.00102
openalex publication_date 2021/07/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let G = (V,E,w) be a weighted undirected graph on |V| = n vertices and |E| = m edges, let k ≥ 1 be any integer, and let ε< 1 be any parameter. We present the following results on fast constructions of spanners with near-optimal sparsity and lightness, which culminate a long line of work in this area. (By near-optimal we mean optimal under Erdős' girth conjecture and disregarding the ε-dependencies.) - There are (deterministic) algorithms for constructing (2k-1)(1+ε)-spanners for G with a near-optimal sparsity of O(n1/k log(1/ε)/ε)). The first algorithm can be implemented in the pointer-machine model within time O(mα(m,n) log(1/ε)/ε) + SORT(m)), where α( , ) is the two-parameter inverse-Ackermann function and SORT(m) is the time needed to sort m integers. The second algorithm can be implemented in the WORD RAM model within time O(m log(1/ε)/ε)). - There is a (deterministic) algorithm for constructing a (2k-1)(1+ε)-spanner for G that achieves a near-optimal bound of O(n1/kpoly(1/ε)) on both sparsity and lightness. This algorithm can be implemented in the pointer-machine model within time O(mα(m,n) poly(1/ε) + SORT(m)) and in the WORD RAM model within time O(m α(m,n) poly(1/ε)). The previous fastest constructions of (2k-1)(1+ε)-spanners with near-optimal sparsity incur a runtime of is O(min\m(n1+1/k) + nlog n,k n2+1/k\), even regardless of the lightness. Importantly, the greedy spanner for stretch 2k-1 has sparsity O(n1/k) -- with no ε-dependence whatsoever, but its runtime is O(m(n1+1/k + nlog n)). Moreover, the state-of-the-art lightness bound of any (2k-1)-spanner is poor, even regardless of the sparsity and runtime.