非表示:
キーワード:
-
要旨:
Let G(V, E) be an undirected weighted graph with |V| = n, |E| = m. Recently
Thorup and
Zwick introduced a remarkable data-structure that stores all
pairs approximate distance information implicitly in o(n2) space,
and yet answers any approximate distance query in constant time.
They named this data-structure approximate
distance oracle because of this feature. Given an integer k < 1,
a (2k-1)-approximate distance oracle requires O(kn1+1/k) space
and answers a (2k-1)-approximate distance query in O(k) time.
Thorup and Zwick showed that a (2k - 1)-approximate
distance oracle can be computed in O(kmn1/k) time,
and posed the following question : Can (2k - 1)-approximate
distance oracle be computed in Õ(n2) time? In this paper,
we answer their question in affirmative for unweighted graphs.
We present an algorithm that computes (2k -1)-approximate
distance oracle for a given unweighted graph in Õ(n2) time.
One of the new ideas used in the improved
algorithm also leads to the first linear time algorithm for
computing an optimal size (2, 1)-spanner of an unweighted graph.
