Return to search

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.

Identiferoai:union.ndltd.org:MIT/oai:dspace.mit.edu:1721.1/30484
Date05 July 2004
CreatorsBadoiu, Mihai, Indyk, Piotr, Sidiropoulos, Anastasios
Source SetsM.I.T. Theses and Dissertation
Languageen_US
Detected LanguageEnglish
Format8 p., 6685848 bytes, 331083 bytes, application/postscript, application/pdf
RelationMassachusetts Institute of Technology Computer Science and Artificial Intelligence Laboratory

Page generated in 0.0018 seconds