Fast C-K-R Partitions of Sparse Graphs

Abstract

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.

15 pages, title changed, a small error in the running time was fixed. Many errors in English were eliminated