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](http://en.wikipedia.org/wiki/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?