License: Creative Commons Attribution-NoDerivs 3.0 Unported license (CC BY-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2013.209
URN: urn:nbn:de:0030-drops-39353
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2013/3935/
Go to the corresponding LIPIcs Volume Portal

Cygan, Marek ; Grandoni, Fabrizio ; Kavitha, Telikepalli

On Pairwise Spanners

pdf-format:
23.pdf (0.6 MB)

Abstract

Given an undirected n-node unweighted graph G = (V, E), a spanner with stretch function f(.) is a subgraph H \subseteq G such that, if two nodes are at distance d in G, then they are at distance at most f(d) in H. Spanners are very well studied in the literature. The typical goal is to construct the sparsest possible spanner for a given stretch function.

In this paper we study pairwise spanners, where we require to approximate the u-v distance only for pairs (u,v) in a given set P \subseteq V x V. Such P-spanners were studied before [Coppersmith,Elkin'05] only in the special case that f(.) is the identity function, i.e. distances between relevant pairs must be preserved exactly (a.k.a. pairwise preservers).

Here we present pairwise spanners which are at the same time sparser than the best known preservers (on the same P) and of the best known spanners (with the same f(.)).
In more detail, for arbitrary P, we show that there exists a P-spanner of size O(n(|P|log n)^{1/4}) with f(d) = d + 4 log n. Alternatively, for any epsislon > 0, there exists a P-spanner of size O(n|P|^{1/4} sqrt{(log n) / epsilon}) with f(d) = (1 + epsilon)d + 4. We also consider the relevant special case that there is a critical set of nodes S \subseteq V, and we wish to approximate either the distances within nodes in S or from nodes in S to any other node. We show that there exists an (S x S)-spanner of size O(n sqrt{|S|}) with f(d) = d + 2, and an (S x V)-spanner of size O(n sqrt{|S| log n}) with f(d) = d + 2 log n. All the mentioned pairwise spanners can be constructed in polynomial time.

BibTeX - Entry

@InProceedings{cygan_et_al:LIPIcs:2013:3935,
  author =	{Marek Cygan and Fabrizio Grandoni and Telikepalli Kavitha},
  title =	{{On Pairwise Spanners}},
  booktitle =	{30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)},
  pages =	{209--220},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-50-7},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{20},
  editor =	{Natacha Portier and Thomas Wilke},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2013/3935},
  URN =		{urn:nbn:de:0030-drops-39353},
  doi =		{10.4230/LIPIcs.STACS.2013.209},
  annote =	{Keywords: Undirected graphs, shortest paths, additive spanners, distance preservers}
}

Keywords: Undirected graphs, shortest paths, additive spanners, distance preservers
Collection: 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)
Issue Date: 2013
Date of publication: 26.02.2013

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI