Approximate Distance Oracle Flashcards
1
Q
What is the functionality of the approximate distance oracle?
What are its parameters?
Give examples of naive solutions.
A
Given weighted and undirected graph, we want to compute a small data structure that can answer distance questions efficiently and with mul-approximation.
Parameters:
S - size of the data structure
Q - Question time
t - quality of approximation
p - inital computation tim
2
Q
Assume we want to compute all pairs initialy.
Assume we don’t want to compute anything initially.
What are the values of S,Q,T,P for each case?
A
S = n^2, Q = 1, T = 1, P = n^3
S = n^2, q = n^2, Q = 1, P = 1
3
Q
A
4
Q
A
5
Q
A
6
Q
A
7
Q
Write definitions
and space
A
8
Q
A
9
Q
Describe query(u,v)
A
10
Q
A
11
Q
Define C(u) and mention the two observations
A
12
Q
A
13
Q
Write the efficient algorithm for finding the path to B(u)
A
