Advances in Directed Spanners
Nov 16, 2011
ABSTRACT:
A k-spanner of a weighted graph is a subset of edges, which preserves distances in the original graph up to a multiplicative factor k. Spanners have numerous applications, such as efficient routing, simulating synchronized protocols in unsynchronized networks, parallel, distributed and streaming algorithms for approximating shortest paths and algorithms for distance oracles. Applications, which are only specific to directed spanners are property testing, property reconstruction and key management in access control hierarchies.
The talk will cover recent advances in approximation algorithms for Directed K-Spanner -- computational problem of finding the sparsest k-spanner of a given directed graph. Improvements in approximation for this basic problem can be naturally translated to different generalisations and related problems, such as Directed Steiner Forest, Client-Server k-spanner and others (joint work with Berman, Bhattacharyya, Makarychev and Raskhodnikova, ICALP 2011).
Constructions of directed spanners for specific graph families are of independent interest, because in general Directed K-Spanner problem is known to be Label-Cover hard to approximate. We will consider almost optimal constructions of directed k-spanners for low-dimensional posets (joint work with Berman, Bhattacharyya, Grigorescu, Raskhodnikova, and Woodruff, ICALP 2011).
A k-spanner of a weighted graph is a subset of edges, which preserves distances in the original graph up to a multiplicative factor k. Spanners have numerous applications, such as efficient routing, simulating synchronized protocols in unsynchronized networks, parallel, distributed and streaming algorithms for approximating shortest paths and algorithms for distance oracles. Applications, which are only specific to directed spanners are property testing, property reconstruction and key management in access control hierarchies.
The talk will cover recent advances in approximation algorithms for Directed K-Spanner -- computational problem of finding the sparsest k-spanner of a given directed graph. Improvements in approximation for this basic problem can be naturally translated to different generalisations and related problems, such as Directed Steiner Forest, Client-Server k-spanner and others (joint work with Berman, Bhattacharyya, Makarychev and Raskhodnikova, ICALP 2011).
Constructions of directed spanners for specific graph families are of independent interest, because in general Directed K-Spanner problem is known to be Label-Cover hard to approximate. We will consider almost optimal constructions of directed k-spanners for low-dimensional posets (joint work with Berman, Bhattacharyya, Grigorescu, Raskhodnikova, and Woodruff, ICALP 2011).