Graph spanners are sparse subgraphs which approximately (additively or multiplicatively) preserve all pairwise shortest-path distances in an input graph. In this thesis we study the problem of computing a graph spanner when the edges of the input graph are distributed across two or more sites. The goal is for the sites to minimize the communication used to output a spanner. Assuming the Message Passing Model (where sites only communicate with a coordinator) we present the first tradeoffs for total communication versus the quality of the spanners computed, for two or more sites. In particular we obtain upper and lower bounds on the communication complexity for multiplicative (2k-1) spanners and additive k spanners.
The talk will primarily emphasis our new algorithms for multiplicative (2k-1) spanners. These algorithms include randomized and deterministic algorithms and both variants achieve the same communication complexity (up to polylog factors).
Advisor: David Woodruff