Graph Theory: Find the Jordan center?

Question

I'm trying to find the set of vertices that minimizes their distance to other vertices on a weighted graph. Based on a cursory wikipedia search, I think that this is called the Jordan Center. What are some good algorithms for finding it?

Right now, my plan is to get a list of the weight for each branch emanating from a given vertex. The vertices whose weights have the smallest relative difference will be the central ones. Any other ideas?

I'm using Java, but helpful answers don't necessarily need to be Java specific.

Answer 1

I woluld first use Dijkstra algorithm (it has to be run for each verticle) for computng shortest distances between all pairs of verticles - there are also some more efficient algorithms for that like Floyd-Warshall. Then for each verticle V you have to find Vm - the largest distance to any other verticles amongs the data retuirned form Dijkstra algorithm. Then, the verticles with the smallest Vm are the one in the graph center. Pseudocode:

int n = number of verticles;
int[][] D = RunDijkstraOrWarshall()
// D[a,b] = length of shortest path from a to b
int[] Vm = new int[n];
for(int i=0; i<n i++)
{
   Vm[i] = 0
   for(int j=0; j<n; j++) 
   {
     if (Vm[i] < D[i,j]) Vm[i] = D[i,j];
   }  
}

minVm = int.Max;
for(int i=0; i<n ;i++)
{
  if (minVm < Vm[i]) minVm = Vm[i];
}

for(int i=0; i<n ;i++)
{
  if (Vm[i] == minVm)
  {
     // graph center contans i
  }

}

Answer 2

Three algorithms for graph center problem are presented in this MSc thesis: A distributed algorithm for the graph center problem.