Assume you have a connected, unweighted, undirected graph of $48$ nodes. Now imagine you are allowed to choose $6$ nodes and label them special. (In the general case, we select $K$ nodes to be special among the $N$ total nodes in the graph, where $K < N$.) We'll call the other $42$ nodes generic.
Once the $6$ special nodes are chosen, new edges are formed between every pair of special nodes. (To speed travel across remote locations within the graph.)
I have a few related questions:
- Is there a single, already-documented algorithm that is precisely designed to solve this problem? Namely, it determines the placement of the special nodes such that the average distance from any generic node to its nearest special node is minimized?
- Am I solving the same problem if I rephrase the question above to read "... the average distance between any two nodes in the graph (with the new special edges added) is minimized?"
- What types of graphs, and graph theory terms, are related to solving this type of problem? Obviously shortest-path type questions arise. But is there a concept such as "coverage"?
The goal stated in very generic terms is to be able to traverse, as quickly as possible, from any arbitrary node in the graph to any other arbitrary node.
For some more context, this graph theory question was inspired by the board game Pandemic. A few colleagues and I have tried searching the web / Wikipedia but haven't come across anything definitive yet.