About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
SIAM Journal on Discrete Mathematics
Paper
Sparse distance preservers and additive spanners
Abstract
For an unweighted graph G = (V,E), G′ = (V,E′) is a subgraph if E′ ⊆ E, and G″ = (V″, E′, ω) is a Steiner graph if V ⊆ V″, and for any pair of vertices u, w ∈ V, the distance between them in G″ (denoted d G″(u,w)) is at least the distance between them in G (denoted d G(u,w)). In this paper we introduce the notion of distance preserver. A subgraph (resp., Steiner graph) G′ of a graph G is a subgraph (resp., Steiner) D-preserver of G if for every pair of vertices u, w ∈ V with d G(u,w) ≥ D, d G′(u, w) = d G(u, w). We show that any graph (resp., digraph) has a subgraph D-preserver with at most O(n 2/D) edges (resp., arcs), and there are graphs and digraphs for which any undirected Steiner D-preserver contains Ω(n 2/D) edges. However, we show that if one allows a directed Steiner (diSteiner) D-preserver, then these bounds can be improved. Specifically, we show that for any graph or digraph there exists a diSteiner D-preserver with O(n 2·log D/D·log n) arcs, and that this result is tight up to a constant factor. We also study D-preserving distance labeling schemes, that are labeling schemes that guarantee precise calculation of distances between pairs of vertices that are at a distance of at least D one from another. We show that there exists a D-preserving labeling scheme with labels of size O(n/D log 2 n), and that labels of size Ω(n/D log D) are required for any D-preserving labeling scheme. © 2006 Society for Industrial and Applied Mathematics.