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 |
| _version_ | 1826214046528962560 |
|---|---|
| author | Badoiu, Mihai Indyk, Piotr Sidiropoulos, Anastasios |
| author_facet | Badoiu, Mihai Indyk, Piotr Sidiropoulos, Anastasios |
| author_sort | Badoiu, Mihai |
| collection | MIT |
| description | 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. |
| first_indexed | 2024-09-23T15:58:57Z |
| id | mit-1721.1/30484 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T15:58:57Z |
| publishDate | 2005 |
| record_format | dspace |
| spelling | mit-1721.1/304842019-04-11T06:23:31Z A Constant-Factor Approximation Algorithm for Embedding Unweighted Graphs into Trees Badoiu, Mihai Indyk, Piotr Sidiropoulos, Anastasios AI embeddings approximation algorithms 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. 2005-12-22T01:35:27Z 2005-12-22T01:35:27Z 2004-07-05 MIT-CSAIL-TR-2004-045 AIM-2004-015 http://hdl.handle.net/1721.1/30484 en_US Massachusetts Institute of Technology Computer Science and Artificial Intelligence Laboratory 8 p. 6685848 bytes 331083 bytes application/postscript application/pdf application/postscript application/pdf |
| spellingShingle | AI embeddings approximation algorithms trees Badoiu, Mihai Indyk, Piotr Sidiropoulos, Anastasios A Constant-Factor Approximation Algorithm for Embedding Unweighted Graphs into Trees |
| title | A Constant-Factor Approximation Algorithm for Embedding Unweighted Graphs into Trees |
| title_full | A Constant-Factor Approximation Algorithm for Embedding Unweighted Graphs into Trees |
| title_fullStr | A Constant-Factor Approximation Algorithm for Embedding Unweighted Graphs into Trees |
| title_full_unstemmed | A Constant-Factor Approximation Algorithm for Embedding Unweighted Graphs into Trees |
| title_short | A Constant-Factor Approximation Algorithm for Embedding Unweighted Graphs into Trees |
| title_sort | constant factor approximation algorithm for embedding unweighted graphs into trees |
| topic | AI embeddings approximation algorithms trees |
| url | http://hdl.handle.net/1721.1/30484 |
| work_keys_str_mv | AT badoiumihai aconstantfactorapproximationalgorithmforembeddingunweightedgraphsintotrees AT indykpiotr aconstantfactorapproximationalgorithmforembeddingunweightedgraphsintotrees AT sidiropoulosanastasios aconstantfactorapproximationalgorithmforembeddingunweightedgraphsintotrees AT badoiumihai constantfactorapproximationalgorithmforembeddingunweightedgraphsintotrees AT indykpiotr constantfactorapproximationalgorithmforembeddingunweightedgraphsintotrees AT sidiropoulosanastasios constantfactorapproximationalgorithmforembeddingunweightedgraphsintotrees |