A Constant-Factor Approximation Algorithm for Embedding Unweighted Graphs into Trees

Author(s)
Badoiu, Mihai; Indyk, Piotr; Sidiropoulos, Anastasios
Thumbnail
DownloadMIT-CSAIL-TR-2004-045.ps (6529.Kb)
Additional downloads
Metadata
Show full item record
Abstract
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.
Date issued
2004-07-05
URI
http://hdl.handle.net/1721.1/30484
Other identifiers
MIT-CSAIL-TR-2004-045
AIM-2004-015
Series/Report no.
Massachusetts Institute of Technology Computer Science and Artificial Intelligence Laboratory
Keywords
AI, embeddings, approximation algorithms, trees
Collections