Let's say we have a graph $G$ with $|V|$ nodes. We wish to select the smallest set of nodes $S$ that:
$dis(i, j) \le k, \forall i \in S, j\in V-S$,
where $k$ denotes a certain distance threshold.
Smallest means the least number of nodes.
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this communityLet's say we have a graph $G$ with $|V|$ nodes. We wish to select the smallest set of nodes $S$ that:
$dis(i, j) \le k, \forall i \in S, j\in V-S$,
where $k$ denotes a certain distance threshold.
Smallest means the least number of nodes.
This looks quite NP-complete to me (just guessing). Obviously if S is not connected then you split it into connected sub-graphs and solve each one individually. Call two nodes a, b connected if their distance is at most k.
Since this is NP-complete, just a heuristic: Put the nodes in some order. If a comes before b, and a is connected to everyone that b is connected to, then we wouldn't put b into S (because exchanging it with a would be better or the same). This reduces the number of candidates to put into S.
Look for the node with the most connections to nodes not in S and not connected to a node in S, and move it into S. Repeat until everything is connected to S.
A second algorithm: Look for nodes with many connections to nodes not in S and not connected to a node in S, pick one at random, and move it into S. Repeat until everything is connected to S. Count the nodes in S. Then try again until it looks like better solutions are hard to find.
A third algorithm: Same as the second, put prefer nodes with connections that don't have many connections themselves.
That's just some ideas. You can find an optimal S by using backtracking. You definitely prefer a node to put into S that is connected to everyone in S, and if there is no such node then you prefer two nodes that are together connected to everyone not in S. Just try out different things, and measure the time.