0
$\begingroup$

A $t$-spanner graph of a set of points $\{p_i\}$ in the plane is a graph $G = (V, E)$ such that for any pair of vertices $p_i, p_j \in V$, the shortest path distance $d_G(p_i, p_j)$ in $G$ is at most $t \cdot d(p_i, p_j)$, where $d(p_i, p_j)$ is the Euclidean distance between $p_i$ and $p_j$.

In my case, I'm interested in a special type of $t$-spanner where distances are measured only with respect to a fixed root node $r$ (say the origin), i.e., the spanner property only needs to hold between $r$ and any other node $p_i$. Is there a standard name for this?

(In particular I am interested in studying how the weight of such a spanner varies as $t\to1$, assuming that the $p_i$'s are independently and uniformly distributed).

$\endgroup$

0

You must log in to answer this question.