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

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.

• The article: PDF (244,762 bytes)
• Source materials: ZIP (61,383 bytes)
• Original version (pre-July 2011): PDF (287,191 bytes)
• Self citation in BIBTeX (326 bytes)

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
Volume 2009 Published articles