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.

  • $\begingroup$ 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? $\endgroup$ – Saeed May 21 '14 at 11:34
  • $\begingroup$ 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$. $\endgroup$ – linello May 21 '14 at 12:47
  • $\begingroup$ 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. $\endgroup$ – Saeed May 21 '14 at 14:16
  • 1
    $\begingroup$ 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. $\endgroup$ – András Salamon May 23 '14 at 10:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.