DROPS

Document

DOI: 10.4230/LIPIcs.FSTTCS.2010.424

Finding Sparser Directed Spanners

Authors: Piotr Berman, Sofya Raskhodnikova, and Ge Ruan

Published in: LIPIcs, Volume 8, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)

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.

Cite as

Piotr Berman, Sofya Raskhodnikova, and Ge Ruan. Finding Sparser Directed Spanners. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010). Leibniz International Proceedings in Informatics (LIPIcs), Volume 8, pp. 424-435, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{berman_et_al:LIPIcs.FSTTCS.2010.424,
  author =	{Berman, Piotr and Raskhodnikova, Sofya and Ruan, Ge},
  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 =	{Lodaya, Kamal and Mahajan, Meena},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2010.424},
  URN =		{urn:nbn:de:0030-drops-28830},
  doi =		{10.4230/LIPIcs.FSTTCS.2010.424},
  annote =	{Keywords: Approximation algorithms, directed graphs, spanners}
}

Search Results

Documents authored by Ruan, Ge

Finding Sparser Directed Spanners

Abstract

Cite as

Thanks for your feedback!

Could not send message