History

Please fill in your query. A complete syntax description you will find on the General Help page.
Sparse distance preservers and additive spanners. (English)
SIAM J. Discrete Math. 19, No. 4, 1029-1055 (2006).
Summary: For an unweighted graph $G = (V,E)$, $G’ = (V,E’)$ is a subgraph if $E’ \subseteq E$, and $G”= (V”,E”,ω)$ is a Steiner graph if $V \subseteq V”$, and for any pair of vertices $u,w \in 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 \in V$ with $d_G(u,w) \ge 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 \cdot \log D} \over{D \cdot \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} \over{D}} \log^2 n)$, and that labels of size $Ω({{n} \over{D}} \log D)$ are required for any $D$-preserving labeling scheme.