Sparse Sourcewise and Pairwise Distance Preservers
Authors:
- Don CoppersmithDCDon Coppersmith
- Michael ElkinMEMichael Elkin
- 1 January 2006
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Discrete Mathematics
- Vol. 20 (2) , 463-501
Abstract
We introduce and study the notions of pairwise and sourcewise preservers. Given an undirected N-vertex graph G = (V,E) and a set P of pairs of vertices, let G' = (V,H), H \subseteq E, be called a pairwise preserver of G with respect to P if for every pair {u,w} \in P, distG'(u,w) = distG(u,w). For a set S \subseteq V of sources, a pairwise preserver of G with respect to the set of all pairs P = (S \atop 2) of sources is called a sourcewise preserver of G with respect to S . We prove that for every undirected possibly weighted N-vertex graph G and every set P of P = O(N1/2) pairs of vertices of G, there exists a linear-size pairwise preserver of G with respect to P. Consequently, for every subset S \subseteq V of S = O(N1/4) sources, there exists a linear-size sourcewise preserver of G with respect to S. On the negative side we show that neither of the two exponents (1/2 and 1/4) can be improved even when the attention is restricted to unweighted graphs. Our lower bounds involve constructions of dense convexly independent sets of vectors with small Euclidean norms. We believe that the link between the areas of discrete geometry and spanners that we establish is of independent interest and might be useful in the study of other problems in the area of low-distortion embeddings.Keywords
This publication has 21 references indexed in Scilit:
- Lectures on Discrete Geometry2002
- Proximity-preserving labeling schemesJournal of Graph Theory, 2000
- The convex hull of the integer points in a large ballMathematische Annalen, 1998
- Near-Linear Time Construction of Sparse Neighborhood CoversSIAM Journal on Computing, 1998
- A Graph-Theoretic Game and Its Application to the k-Server ProblemSIAM Journal on Computing, 1995
- Routing with Polynomial Communication-Space Trade-OffSIAM Journal on Discrete Mathematics, 1992
- On lipschitz embedding of finite metric spaces in Hilbert spaceIsrael Journal of Mathematics, 1985
- Extensions of Lipschitz mappings into a Hilbert space1984
- On the Linear Independence of Fractional Powers of IntegersJournal of the London Mathematical Society, 1940
- ber die Gitterpunkte auf konvexen KurvenMathematische Zeitschrift, 1926