
Summary: An \((\alpha,\beta)\)-spanner of a graph \(G\) is a subgraph \(H\) such that \(\text{dist}_H(u,w)\leq \alpha\cdot \text{distt}_G(u,w)+\beta\) for every pair of vertices \(u,w\), where dist\(_{G'}(u,w)\) denotes the distance between two vertices \(u\) and \(w\) in \(G'\). It is known that every graph \(G\) has a polynomially constructible \((2\kappa-1,0)\)-spanner (also known as multiplicative \((2\kappa-1)\)-spanner) of size \(O(n^{1+1/\kappa})\) for every integer \(\kappa\geq 1\), and a polynomially constructible \((1,2)\)-spanner (also known as additive 2-spanner) of size \({\widetilde O}(n^{3/2})\). This paper explores hybrid spanner constructions (involving both multiplicative and additive factors) for general graphs and shows that the multiplicative factor can be made arbitrarily close to 1 while keeping the spanner size arbitrarily close to \(O(n)\), at the cost of allowing the additive term to be a sufficiently large constant. More formally, we show that for any constants \(\varepsilon, \lambda > 0\) there exists a constant \(\beta = \beta(\varepsilon, \lambda)\) such that for every \(n\)-vertex graph \(G\) there is an efficiently constructible \((1+ \varepsilon, \beta)\)-spanner of size \(O(n^{1 + \lambda})\).
graph algorithms, spanners, Distance in graphs, Graph algorithms (graph-theoretic aspects), Graph theory (including graph drawing) in computer science, graph partitions
graph algorithms, spanners, Distance in graphs, Graph algorithms (graph-theoretic aspects), Graph theory (including graph drawing) in computer science, graph partitions
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 83 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Top 10% | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Top 10% |
