4
$\begingroup$

I am not familiar with graphs. However, I am curious about a question on graphs. Given a finite set equipped with a metric, is there any studying on the following problem?

Problem: given the metric $d$ for vertexes on $V$, build the undirected graph with the minimum number of edges such that, for each pair of vertices $(v_1, v_2)\in V$, the shortest path from $v_1$ to $v_2$ equals $d(v_1, v_2)$. Is this graph unique?

This kind of graph building would be very important to model depedency of agents on economical dynamic systems.

  • 2
    Why don't you just start with a complete graph, then eliminate any edge $(v_1, v_2)$ for which there is a vertex $v_3$ such that $d(v_1,v_3) + d(v_3,v_2) = d(v_1,v_2)$?2012-10-05
  • 0
    Actually I just want to know if this is a known problem or if there is a field of study for this kind of problem. What would be the complexity of your algorithm? I think it is $O(n^2)$2012-10-05

1 Answers 1