Article ID: | iaor20116456 |
Volume: | 61 |
Issue: | 1 |
Start Page Number: | 141 |
End Page Number: | 160 |
Publication Date: | Sep 2011 |
Journal: | Algorithmica |
Authors: | Emek Yuval |
Keywords: | random search, approximation algorithms, minimum spanning tree |
Low distortion probabilistic embedding of graphs into approximating trees is an extensively studied topic. Of particular interest is the case where the approximating trees are required to be (subgraph) spanning trees of the given graph (or multigraph), in which case, the focus is usually on the equivalent problem of finding a (single) tree with low average stretch. Among the classes of graphs that received special attention in this context are