A preliminary analysis of the Distance Based Critical Node Problem

We discuss how to develop efficient heuristics for the distance based critical node problem, that is the problem of deleting a subset of nodes from a graph G in such a way that the distance between each pair of nodes is as large as possible.