3
$\begingroup$

This is the scenario: There is an undirected graph with n nodes and e edges, all nodes are connected.

The question in the scenario: Every node can be considered as a person in a social network that shares or reads a content. It means that if A is connected to B, C and D, if A shares a content with the network, it will reach directly BCD. It means that to reach all the nodes in the network, it's just necessary that they are adjacent to a node which shared the content.

Q1: is there a way to find the best starting point to reach the entire network? Q2: is there a way to find a smallest path from that point?

I've already looked at salesman problem and prim'algorithm.

Thanks!

1 Answers 1

4

You're trying to find the Jordan center of a graph. That is, the node(s) which have the minimum eccentricity.

One way to calculate this is to run an all-pairs shortest path algorithm on the graph and see which node has the minimum maximum shortest path.

  • 0
    Can you suggest how to find using mathematical models/algorithms the Jordan point? I should know how to continue then..2011-08-11