Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
add comment

1 Answer

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.

share|improve this answer
    
Can you suggest how to find using mathematical models/algorithms the Jordan point? I should know how to continue then.. –  Nicola G Aug 11 '11 at 17:59
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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