# Distance oracles in trees

Given an unweighted tree $T=(V,E)$ what is the minimum number of distance oracles that allow to detect the position in the graph of every node $v$?

A distance oracle is "special node" $u$ of the graph that represents a function $d(u,v)$ giving the distance from $u$ to $v$ in constant time.

I have the intuition that this problem is strictly related to all pair shortest path problem, in particular to the Dijkstra algorithm, but can't find a valid algorithm to detect the oracles. Also a backtracking procedure comes to mind for this kind of problem. Maybe you have a better intuition.

• By "reconstruct the graph topology", do you mean finding an isomorphic graph to original one? If you really looking for topology of graph, then what is your topological space? – Saeed May 21 '14 at 11:34
• Actually it is a tree. And I also have to modify a little the text of the problem. I want to find the minimum number of oracles nodes such that, when asked they allow to detect the position in the tree of a given node $v$. – linello May 21 '14 at 12:47
• I already edited your question and wrote tree instead of graph, but at the same time I was going to edit words "reconstruct the graph topology", to "reconstruct an isomorphic tree", but I was not sure that you mean this, so I didn't edit that part. – Saeed May 21 '14 at 14:16
• I still don't understand the question: in a tree the root can serve as a very effective distance oracle, but this depends on what "detect the position" means. – András Salamon May 23 '14 at 10:35