Fast C-K-R Partitions of Sparse Graphs
  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. 
Manor Mendel, Chaya Schwob