Critical Node Problems - CNP

Benchmark Instances

These sets of benchmark instances have been used in our research on the Critical Node Problem. The first one is that proposed by Ventresca, and it is composed of 16 instances widely used in literature. Such instances are composed of undirected graphs having up to 5000 nodes.
The second one is a set of benchmark instances derived from real problems (airplanes, railroads, social networks, ...) having up to 23133 nodes.

The instance format is depicted here.

  1. Ventresca.zip: 16 instances by Ventresca
  2. RealInstances.zip: 26 instances by Aringhieri, Grosso, Hosteins and Scatamacchia

Best Known Results

In this section, we provide an up to date collection of best known results reporting the performance of published algorithms. Note that such results are obtained running the algorithms with different time limits on different computers. If an algorithm is missing, please let us known via email.

  1. 2016-07-12-CNP-BestKnownHeuristicResults.pdf
  2. 2016-07-12-CNP-BestKnownHeuristicResults.ods
  3. 2016-07-12-CNP-BestKnownHeuristicResults.xls

 

Research