A Constant-Factor Approximation Algorithm for Embedding Unweighted Graphs into Trees
We present a constant-factor approximation algorithm for computing anembedding of the shortest path metric of an unweighted graph into atree, that minimizes the multiplicative distortion.
| Main Authors: | , , |
|---|---|
| Language: | en_US |
| Published: |
2005
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/30484 |
| Summary: | We present a constant-factor approximation algorithm for computing anembedding of the shortest path metric of an unweighted graph into atree, that minimizes the multiplicative distortion. |
|---|