<p>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$?</p>

<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2014-05-21T11:34:25.847Z
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
CC BY-SA 3.0
2014-05-21T12:47:45.400Z
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
CC BY-SA 3.0
2014-05-21T14:16:25.747Z
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
CC BY-SA 3.0
2014-05-23T10:35:23.207Z
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
<graph-theory><graph-algorithms><shortest-path>
Distance oracles in trees
linello
# Distance oracles in trees

(Asked by: username_0 on 2014-05-21)

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.

**Tags:** graph-theory, graph-algorithms, shortest-path
> **Comments:**
> **username_1**: 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?  
> **username_0**: 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$.  
> **username_1**: 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.  
> **username_2**: 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.  

---

## 0 answers

