Two-center algorithm to find minimum of farthest point

Question

I'm trying to come up with an algorithm that allows me to find two vertices in an undirected, weighted graph that minimizes the distance to the farthest point.

Distance of the farthest point is basically the distance between two vertices (u, v) in the graph such that distance(u,v) >= distance(x,y) for any two other vertices in the same graph.

I know how to do this problem for 1 center (meaning one vertex that minimizes the distance to the farthest point). I also read up on the K-center algorithm that allows me to find multiple centers. But I read that the K-center algorithm does not work when k=2. So can anyone tell me what exactly I should do to find 2 centers?

Any help would be greatly appreciated. Thank you!

Answer 1

My algorithm uses the Brute Force method.
For each a pair of vertices (u, v) in G, I calculate the farthest distance from u and v to all other vertices. Then I simply find the minimum.

For example, in a graph G that consists of the vertices A, B, C, D, E. . . I arbitrarily select (A, B) to be the first possible pair. I calculate (A, B)’s distance to C. Let's say A’s distance to C is 4. B’s distance to C is 14. So I select 4 as the distance from C to (A, B) because we are searching for minimum.

I perform this selection for vertices D, E, F... Each vertex will yield a distance to (A, B). Out of those distances, I select the maximum. That will be the furthest distance of all locations in G to (A, B).

Next I perform this selection for all possible pairs of locations, so I will perform this selection for (A, C), (A, D), (B, C), (B, D) and so on.
Once I generated a distance to the farthest point (or vertex) for all pairs of vertices, I simply select the pair that yields the smallest distance.