Berman, Piotr ;
Raskhodnikova, Sofya ;
Ruan, Ge
Finding Sparser Directed Spanners
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 transitiveclosure 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$TCspanner) of a given directed graph, which we refer to as DIRECTED $k$SPANNER (resp., $k$TCSPANNER). 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 = {424435},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897231},
ISSN = {18688969},
year = {2010},
volume = {8},
editor = {Kamal Lodaya and Meena Mahajan},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2010/2883},
URN = {urn:nbn:de:0030drops28830},
doi = {10.4230/LIPIcs.FSTTCS.2010.424},
annote = {Keywords: Approximation algorithms, directed graphs, spanners}
}
2010
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 