ABSTRACT
An (α,Β)-spanner of a graph G is a subgraph H such that d_H(u,w)\le α\cdot d_G(u,w)+Β for every pair of vertices u,w, where d_{G'}(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 (a.k.a. multiplicative (2κ-1)-spanner) of size O(n^{1+1/κ}) for every integer κ\ge 1, and a polynomially constructible (1,2)-spanner (a.k.a. additive 2-spanner) of size \tO(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 constant ε, δ > 0 there exists a constant Β = Β(ε, δ) such that for every n-vertex graph G there is an efficiently constructible (1+ ε, Β)-spanner of size O(n^{1 + δ}). It follows that for any constant ε, δ > 0 there exists a constant Β(ε, δ) such that for any n-vertex graph G = (V,E) there exists an efficiently constructible subgraph (V,H) with O(n^{1 +δ}) edges such that d_H(u,w) \le (1 + ε) d_G(u,w) for every pair of vertices.
- 1.I. Althofer, G. Das, D. Dobkin, D. Joseph and J. Soares, On Sparse Spanners of Weighted Graphs, Discrete & Computational Geometry 9, (1993), 81-100. Google ScholarDigital Library
- 2.Baruch Awerbuch and David Peleg, Sparse partitions, Proc. 31st IEEE Symp. on Foundations of Computer Science, 503-513, October 1990.Google Scholar
- 3.R. D. Carr, S. Doddi, G. Konjevod, M. V. Marathe, On the Red-Blue Set Cover Problem, Proc. 11th ACM-SIAM Symp. on Discrete Algorithms, 2000. Google ScholarDigital Library
- 4.B. Chandra, G. Das, G. Narasimhan and J. Soares, New Sparseness Results on Graph Spanners, Proc. 8th ACM Symp. on Computat. Geometry, 192-201, 1992. Google ScholarDigital Library
- 5.L.P. Chew, There is a planar graph almost as good as the complete graph, 2nd Symp. on Computational Geometry, pages 169-177, 1986. Google ScholarDigital Library
- 6.D.P. Dobkin, S.J. Friedman and K.J. Supowit, Delaunay graphs are almost as good as complete graphs, Proc. 31st IEEE Symp. on Foundations of Computer Science, 1987, 20-26.Google ScholarDigital Library
- 7.D. Dor, S. Halperin, U. Zwick, All pairs almost shortest paths, SIAM Journal on Computing 29, (2000), 1740-1759. Google ScholarDigital Library
- 8.Y. Dodis and S. Khanna, Designing Networks with Bounded Pairwise Distance, Proc. 30th ACM Symp. on Theory of Computing, 1999. Google ScholarDigital Library
- 9.M.-L. Elkin and D. Peleg, The Hardness of Approximating Spanner Problems, Proc. 17th Symp. on Theoretical Aspects of Computer Science, Lille, France, Feb. 2000, 370-381.Google ScholarDigital Library
- 10.M.-L. Elkin and D. Peleg, Strong Inapproximability of the Basic k-Spanner Problem, Proc. 27th Int. Colloq. on Automata, Languages and Programming, Geneva, Switzerland, July 2000, 636-648.Google ScholarDigital Library
- 11.M.-L. Elkin and D. Peleg, The Client-Server 2-Spanner Problem and Applications to Network Design, Technical Report MCS99-24, the Weizmann Institute of Science, 1999. Google ScholarDigital Library
- 12.M.-L. Elkin and D. Peleg, Approximating k-Spanner Problems for k >2, Technical Report MCS00-14, the Weizmann Institute of Science, 2000. Google ScholarDigital Library
- 13.D. Hochbaum, Approximation Algorithms for NP-hard Problems, PWS Publishing Company, Boston, 1997. Google ScholarDigital Library
- 14.G. Kortsarz, On the Hardness of Approximating Spanners, Proc. APPROX., LNCS 1444, Springer-Verlag, New York/Berlin, 135-146, 1998. Google ScholarDigital Library
- 15.G. Kortsarz and D. Peleg, Generating Sparse 2-Spanners, J. Algorithms 17, (1994), 222-236. Google ScholarDigital Library
- 16.C. Li, S. McCormick and D. Simchi-Levi, On the Minimum-Cardinality-Bounded-Diameter and Bounded-cardinality-minimum-diameter Edge Addition Problems, Operation Research Letters 11, (1992), 303-308.Google ScholarDigital Library
- 17.A.L. Liestman and T.C. Shermer, Additive Graph Spanners, Tech. Report No 91-5, Simon Fraser University, 1991.Google Scholar
- 18.A.L. Liestman and T.Shermer, Grid Spanners, Networks 23, (1993), 123-133.Google ScholarCross Ref
- 19.D. Peleg, Distributed Computing: A Locality-Sensitive Approach, SIAM, Philadelphia, PA, 2000. Google ScholarDigital Library
- 20.D. Peleg and A. Schaer, Graph Spanners, J. Graph Theory 13, (1989), 99-116.Google ScholarCross Ref
- 21.D. Peleg and J.D. Ullman, An optimal synchronizer for the hypercube, SIAM J. Computing 18, (1989), 740-747. Google ScholarDigital Library
- 22.R. Wenger. Extremal graphs with no C41 s, C 6 1 s and C 10 1 s. Journal of Combinatorial Theory, Series B 52, (1991), 113-116. Google ScholarDigital Library
Index Terms
- (1 + εΒ)-spanner constructions for general graphs
Recommendations
$(1 + \epsilon,\beta)$-Spanner Constructions for General Graphs
An {\em $(\alpha,\beta)$-spanner} of a graph G is a subgraph H such that $\mathit{dist}_H(u,w)\le \alpha\cdot \mathit{dist}t_G(u,w)+\beta$ for every pair of vertices u,w, where distG'(u,w) denotes the distance between two vertices u and v in G'. It is ...
Outer 1-Planar Graphs
AbstractA graph is outer 1-planar (o1p) if it can be drawn in the plane such that all vertices are in the outer face and each edge is crossed at most once. o1p graphs generalize outerplanar graphs, which can be recognized in linear time, and specialize 1-...
Comments