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!

$\endgroup$

1 Answer 1

4
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Can you suggest how to find using mathematical models/algorithms the Jordan point? I should know how to continue then.. $\endgroup$
    – Nicola G
    Aug 11, 2011 at 17:59
  • $\begingroup$ @NicolaG, run breadth-first search (BFS) from each node v. The number of edges it took to get from v to the last node encountered in a BFS is the eccentricity of v. Once this is completed for all nodes, any node belonging to the set of all nodes with minimum eccentricity represents a good starting point to reach the entire network. $\endgroup$ Nov 14, 2019 at 18:22

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.