you're reading...

SACT talk: Advances in directed spanners

Time: 1:00pm Tuesday 9.

Location: SIT 123 Lecture Theatre

Speaker: Grigory Yaroslavtsev, Pennsylvania State University


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.

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).




No comments yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

Enter your email address to subscribe to receive notifications of new announcements by email.

Join 68 other followers

%d bloggers like this: