Hybrid Stretch and Sourcewise Spanners

by Merav Parter

Oded's comments

What I liked most about Merav's presentation is the suggestion she made at its end by which one can consider a generalized notion of an $f$-spanner, for any integer function $f$. Specifically, an $f$-spanner of a graph G=(V,E) is a subgraph H of G that satisfies $\dist_H(u,v) \leq f(\dist_G(u,v))$ for each pair of vertices $(u,v)\in V^2$.

The standard notion of an $(alpha,beta)$-spanner, which generalizes both the notion of an $\alpha$-multiplicative spanner (i.e., $\beta=0$) and the notion of a $\beta$-additive spanner (i.e., $\alpha=1$), is obtained by considering the linear function $f(x) = \alpha\cdot x + b$. Merav's paper focuses on non-linear functions of the form $f_k(1) = 2k-1$ and $f_k(x) = k\cdot x$ for every $x\geq 2$. It obtains bounds that are compareable to that of $(2k-1)$-spanners by avoiding the reduction of the general case (i.e., arbitrary vertex pairs) to the case of adjacent vertuices (i.e., distance one).

The aforementioned special case of $f_k$ is referred in the paper as $k$-hybrid spanners, and in addition ``sourcewise spanners'' are also considsered.

The original abstract

See paper.

Back to list of Oded's choices.