when quoting this document, please refer to the following
DOI:
URN: urn:nbn:de:0030-drops-28830
URL:

; ;

### Finding Sparser Directed Spanners

 pdf-format:

### 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},
URL =		{http://drops.dagstuhl.de/opus/volltexte/2010/2883},
URN =		{urn:nbn:de:0030-drops-28830},
doi =		{http://dx.doi.org/10.4230/LIPIcs.FSTTCS.2010.424},
annote =	{Keywords: Approximation algorithms, directed graphs, spanners}
}


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

DROPS-Home | Fulltext Search | Imprint