Andrea Grosso We consider the Critical Node Problem: given an undirected graph and an integer number K, at most K nodes have to be deleted from the graph in order to minimize a connectivity measure in the residual graph. We combine the basic steps used in common greedy algorithms with some flavour of local search, in order … Read more
We consider the problem of deleting a limited number of nodes from a graph in order to minimize a connectivity measure between the surviving nodes. We prove that the problem is $NP$-complete even on quite particular types of graph, and define a dynamic programming recursion that solves the problem in polynomial time when the graph … Read more
In this paper we deal with the critical node problem, where a given number of nodes has to be removed from an undirected graph in order to maximize the disconnections between the node pairs of the graph. We propose an integer linear programming model with a non-polynomial number of constraints but whose linear relaxation can … Read more
In this paper we deal with the Critical Node Problem (CNP), i.e., the problem of searching for a given number K of nodes in a graph G, whose removal minimizes the number of connections between pairs of nodes in the residual graph. While the NP-completeness of this problem for general graphs has been already established … Read more
In this paper we propose a Monotonic Basin Hopping approach and its population-based variant Population Basin Hopping to solve the problem of packing equal and unequal circles within a circular container with minimum radius. Extensive computational experiments have been performed both to analyze the problem at hand, and to choose in an appropriate way the … Read more
In this paper we consider global optimization algorithms based on multiple local searches for the Molecular Distance Geometry Problem (MDGP). Three distinct approaches (Multistart, Monotonic Basin Hopping, Population Basin Hopping) are presented and for each of them a computational analysis is performed. The results are also compared with those of two other approaches in the … Read more
When dealing with extremely hard global optimization problems, i.e. problems with a large number of variables and a huge number of local optima, heuristic procedures are the only possible choice. In this situation, lacking any possibility of guaranteeing global optimality for most problem instances, it is quite difficult to establish rules for discriminating among different … Read more
In the DIMACS benchmark suite for the maximum clique problem, the best known solution for test C2000.9 is a 78 nodes clique; optimality is not proved. We present a 79 nodes clique emerged during the testing of a heuristic algorithm. ArticleDownload View PDF