Distance oracles for unweighted graphs: breaking the quadratic barrier with constant additive error

Baswana, Surender ; Gaur, Akshay ; Sen, Sandeep ; Upadhyay, Jayant (2008) Distance oracles for unweighted graphs: breaking the quadratic barrier with constant additive error 35th International Colloquium on Automata, Languages and Programming .

[img]
Preview
PDF - Author Version
173kB

Official URL: http://www.cse.iitd.ac.in/~ssen/conf/icalp08.pdf

Abstract

Thorup and Zwick, in the seminal paper [Journal of ACM, 52(1), 2005, pp 1-24], showed that a weighted undirected graph on n vertices can be preprocessed in subcubic time to design a data structure which occupies only subquadratic space, and yet, for any pair of vertices, can answer distance query approximately in constant time. The data structure is termed as approximate distance oracle. Subsequently, there has been improvement in their preprocessing time, and presently the best known algorithms [4, 3] achieve expected O(n2) preprocessing time for these oracles. For a class of graphs, these algorithms indeed run in Θ(n2) time. In this paper, we are able to break this quadratic barrier at the expense of introducing a (small) constant additive error for unweighted graphs. In achieving this goal, we have been able to preserve the optimal size-stretch trade offs of the oracles. One of our algorithms can be extended to weighted graphs, where the additive error becomes 2. ωmax(u, υ) - here ωmax(u, υ) is the heaviest edge in the shortest path between vertices u, υ.

Item Type:Article
Source:Copyright of this article belongs to European Association for Theoretical Computer Science.
ID Code:90268
Deposited On:08 May 2012 14:37
Last Modified:19 May 2016 04:32

Repository Staff Only: item control page