Tuesday, March 10, 2009
Sofya Raskhodnikova
Chair: abhi shelat
Advisor:
OLSSON 009, 15:30:00
An Invited Talk
Transitive-closure Spanners
ABSTRACT
We define the notion of a transitive-closure spanner of a directed graph. A transitive-closure spanner of a given directed graph is a graph of small diameter that preserves connectivity of the original graph. Formally, given a directed graph G = (V,E) and an integer k>=1, a k-transitive-closure-spanner (k-TC-spanner) of G is a directed graph H = (V, E_H) that has (1) the same transitive-closure as G and (2) diameter at most k. These spanners were studied implicitly in sublinear algorithms, access control, and data structures, and properties of these spanners have been rediscovered over the span of 20 years. We bring these areas under the unifying framework of TC-spanners. We abstract the common task implicitly tackled in these diverse applications as the problem of constructing sparse TC-spanners.
We study the size of the sparsest k-TC-spanners for specific graph families, as well as the computational task of finding the sparsest k-TC-spanner for a given input graph. We present new positive and negative results on both fronts. In the talk, we will explain some ramifications of these results for testing monotonicity of functions.
Joint work with Arnab Bhattacharyya, Elena Grigorescu, Kyomin Jung and David Woodruff