Home | Bookmarks | Papers | Blog |
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(n3/2) space and constant query time for stretch 3 paths. Special cases of our data structures can retrieve stretch 2 paths with O(n3/2) space and stretch 3 paths with O(n) space, albeit at the cost of O(\sqrt n) query time.