# Steiner points in tree metrics don't (really) help

Anupam Gupta

Research output: Chapter in Book/Report/Conference proceedingConference contribution

## Abstract

Consider an edge-weighted tree T = (V, E, w : E &rarrtl; R +), in which a subset R of the nodes (called the required nodes) are colored red and the remaining nodes in S = V\R 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. We now ask the following question: Is it possible to define another weighted tree T* = (R, E*, w* : E* &rarrtl; 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 &agr; such that dT(u, v) ≤ dT* (u, v) ≤ dT (u, v) for any two red vertices u, &squv; a R? We answer this question in the affirmative, and give a linear time algorithm to obtain a tree T* with &agr; ≤ 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 &OHgr;(g) when approximated by a tree.

Original language English (US) Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms 220-227 8 Published - 2001 2001 Operating Section Proceedings, American Gas Association - Dallas, TX, United StatesDuration: Apr 30 2001 → May 1 2001

### Publication series

Name Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

### Other

Other 2001 Operating Section Proceedings, American Gas Association United States Dallas, TX 4/30/01 → 5/1/01

• Algorithms
• Measurement
• Theory
• Verification

## ASJC Scopus subject areas

• Software
• General Mathematics

## Fingerprint

Dive into the research topics of 'Steiner points in tree metrics don't (really) help'. Together they form a unique fingerprint.