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