Answers are grounded in this paper and cite their sources.
Consider an edge-weighted tree T = (V, E, w : E âtl; R+), in which a subset R of the nodes (called the required nodes) are colored red and the remaining nodes in S = V\ are colored black (and called the Steiner nodes). The shortest-path distance according to the edge-weights defines a metric dT on the vertex set V. now ask the following question: Is it possible to define another weighted tree T* = (R, E*, w* : E* âtl; R+), this time on just the red vertices so that the shortest-path metric dT* induced by T* on the vertices in R is âcloseâ to the metric dT restricted to the red vertices? I.e., does there exist a weighted tree T* = (R, E*, c*) and a (small) constant such that dT(u, v) ⤠dT* (u, v) ⤠dT(u, v) for any two red vertices u, v â R? answer this question in the affirmative, and give a linear time algorithm to obtain a tree T* with ⤠8. We also give two applications of this result: an upper bound, in which we show that emulating multicasts using unicasts can be almost as good as general multicasts for certain performance measures; and a lower bound, in which we give a simple combinatorial proof of the fact that the metric generated by a graph of girthg must suffer a distortion of at least (g) when approximated by a tree.
No takes yet. Share an insight, caveat, or question.
Anupam Gupta (2001) studied this question.