Back to Search
Start Over
(1 + ε )-SPANNER CONSTRUCTIONS FOR GENERAL GRAPHS.
- Source :
-
SIAM Journal on Computing . 2004, Vol. 33 Issue 2, p608-631. 24p. - Publication Year :
- 2004
-
Abstract
- An (α,β)-spanner of a graph G is a subgraph H such that distH(u,w) ≤ α disttG (u, w) + β for every pair of vertices u, w, where distG', (u, w) denotes the distance between two vertices u and v in G'. It is known that every graph G has a polynomially constructible (2κ - 1,0)- spanner (also known as multiplicative (2κ - 1)-spanner) of size O(n1+1/κ) for every integer it κ ≥ 1, and a polynomially constructible (1,2)-spanner (also known as additive 2-spanner) of size O(n&frac32;). 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 constant ϵ, λ > 0 there exists a constant β = β(ϵ, λ) such that for every n-vertex graph G there is an efficiently constructible (1 + ϵ, β)-spanner of size O(n1+λ). [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 00975397
- Volume :
- 33
- Issue :
- 2
- Database :
- Academic Search Index
- Journal :
- SIAM Journal on Computing
- Publication Type :
- Academic Journal
- Accession number :
- 13266066
- Full Text :
- https://doi.org/10.1137/S0097539701393384