Chicago Journal of Theoretical Computer Science

Volume 2009

Article 2

Published by Dept. CS U. Chicago. Copyright 2009 CJTCS and the author.


Fast C-K-R Partitions of Sparse Graphs

Manor Mendel
Computer Science Division
The Open University of Israel
and
Chaya Schwob
Computer Science Division
The Open University of Israel

July 16, 2009
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.

Submitted September 10, 2008, revised version submitted June22 2009, published July 16 2009.

DOI: 10.4086/cjtcs.2009.002
[] Volume 2009, Article 1 [] Article 3
[back] Volume 2009 [back] Published articles
[CJCTS home]