Published by Dept. CS U. Chicago. Copyright 2009 CJTCS and the author.
We present fast algorithms for constructing probabilistic embeddings
and approximate distance oracles in sparse graphs. The main ingredient is a
fast algorithm for sampling the probabilistic partitions of Calinescu,
Karloff, and Rabani in sparse graphs.
Submitted September 10, 2008, revised version submitted June22 2009, published July 16 2009.