A Constant-Factor Approximation Algorithm for Embedding Unweighted Graphs into Trees
| Data(s) |
08/10/2004
08/10/2004
05/07/2004
|
|---|---|
| Resumo |
We present a constant-factor approximation algorithm for computing an embedding of the shortest path metric of an unweighted graph into a tree, that minimizes the multiplicative distortion. |
| Formato |
8 p. 981451 bytes 626039 bytes application/postscript application/pdf |
| Identificador |
AIM-2004-015 |
| Idioma(s) |
en_US |
| Relação |
AIM-2004-015 |
| Palavras-Chave | #AI #embeddings #approximation algorithms #trees |
