Home | Bookmarks | Papers | Blog |

An approximate distance query data structure is a compact representation of a graph. It allows querying for approximate shortest paths between any pair of vertices in the graph. Thorup and Zwick proved that any approximate data structure that allows retrieval of stretch

We present data structures that, for sparse graphs, substantially
break the Thorup-Zwick lower bound barrier, albeit at the expense of
slightly higher query time. For instance, for the realistic scenario
of a graph with **n** vertices and average degree **\Theta( log
n)**, the data structure of Thorup and Zwick requires
**O(n ^{3/2})** space and constant query time for stretch

Postscript, PDF.

Last modified: Tue Jan 11 21:33:12 CST 2011