Find n nodes farthest away from each other

Question

I'm looking for an algorithm that gives me the n nodes that are the farthest away from each other.

Can this be accomplished relatively efficiently?

To clarify my question: I think of the problem as a variant of the opposite of the travelling salesman problem. We have this graph:

The distance matrix looks like this:

    a   b   c   d   e   f
a   0   184 222 177 216 231
b   184 0   45  123 128 200
c   222 45  0   129 121 203
d   177 123 129 0   46  83
e   216 128 121 46  0   83
f   231 200 203 83  83  0

For example, the salesman needs to visit any 4 nodes shown above. He must be on the road between all nodes he visits as long as possible. Which nodes would he visit?

My guess is we're looking for the 4 nodes with the maximum average distance between them. Is there a reasonably efficient, preferably non-exponential, way to do this? What if I don't need an exact solution to the problem?

Answer 1

To find the four longest distances, you need to search over all the distances. So for n nodes, you need to loop through n^2 distances, and so something like:

if dist > smallest_max
  replace smallest max in array of four maximums with dist
  recalculate the smallest max from array

This is O(n^2), which is not good but it's not exponential like traveling salesman.