2008 | OriginalPaper | Buchkapitel
Distance Oracles for Unweighted Graphs: Breaking the Quadratic Barrier with Constant Additive Error
verfasst von : Surender Baswana, Akshay Gaur, Sandeep Sen, Jayant Upadhyay
Erschienen in: Automata, Languages and Programming
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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
(
n
2
) preprocessing time for these oracles. For a class of graphs, these algorithms indeed run in
Θ
(
n
2
) 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 ·
w
max
(
u
,
v
) - here
w
max
(
u
,
v
) is the heaviest edge in the shortest path between vertices
u
,
v
.