We present basic graph decomposition lemmas and show how they apply as key ingredients in the probabilistic embedding theorem stating that every n point metric space probabilistically embeds in ul-trametrics with distortion O(logn) and in the proof of a similar bound for the spreading metrics paradigm in undirected graphs. This provides a unified framework for these metric methods which have numerous algorithmic applications.
展开▼
