License: Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2010.424
URN: urn:nbn:de:0030-drops-28830
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2010/2883/
Go to the corresponding LIPIcs Volume Portal

Berman, Piotr ; Raskhodnikova, Sofya ; Ruan, Ge

Finding Sparser Directed Spanners

pdf-format:
37.pdf (0.7 MB)

Abstract

A spanner of a graph is a sparse subgraph that approximately preserves distances in the original graph. More precisely, a subgraph $H = (V,E_H)$ is a $k$-spanner of a graph $G=(V,E)$ if for every pair of vertices $u,v \in V$, the shortest path distance $dist_H(u,v)$ from $u$ to $v$ in $H$ is at most $k.dist_G(u,v)$. We focus on spanners of directed graphs and a related notion of transitive-closure spanners. The latter captures the idea that a spanner should have a small diameter but preserve the connectivity of the original graph. We study the computational problem of finding the sparsest $k$-spanner (resp., $k$-TC-spanner) of a given directed graph, which we refer to as DIRECTED $k$-SPANNER (resp., $k$-TC-SPANNER). We improve all known approximation algorithms for these problems for $k\geq 3$. (For $k=2$, the current ratios are tight, assuming P$\neq$NP.) Along the way, we prove several structural results about the size of the sparsest spanners of directed graphs.

BibTeX - Entry

@InProceedings{berman_et_al:LIPIcs:2010:2883,
  author =	{Piotr Berman and Sofya Raskhodnikova and Ge Ruan},
  title =	{{Finding Sparser Directed Spanners}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)},
  pages =	{424--435},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-23-1},
  ISSN =	{1868-8969},
  year =	{2010},
  volume =	{8},
  editor =	{Kamal Lodaya and Meena Mahajan},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2010/2883},
  URN =		{urn:nbn:de:0030-drops-28830},
  doi =		{10.4230/LIPIcs.FSTTCS.2010.424},
  annote =	{Keywords: Approximation algorithms, directed graphs, spanners}
}

Keywords: Approximation algorithms, directed graphs, spanners
Collection: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)
Issue Date: 2010
Date of publication: 14.12.2010

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