We present two metaheuristics for the Critical Node Problem, that is, the maximal fragmentation of a graph through the deletion of nodes. The two metaheuristics are based on the Iterated Local Search and Variable Neighborhood Search frameworks. Their main characteristic is to exploit two smart and computationally efficient neighborhoods which we show can be implemented far more efficiently than the classical neighborhood based on the exchange of any two nodes in the graph, and which we prove is equivalent to the classical neighborhood in the sense that it yields the same set of neighbors. Solutions to improve the overall running time without deteriorating the quality of the solution computed are also illustrated. The results of the proposed metaheuristics outperform those currently available in literature. © 2016 Wiley Periodicals, Inc. NETWORKS, Vol. 67(3), 209–221 2016

In this paper we discuss the optimal design of logical topologies in wavelength-routed WDM networks supporting unicast and multicast transfer of IP datagrams. We first explain the key aspects of the problem, emphasizing the fact that in IP networks the routing algorithms are an input to the optimization problem, not an optimization target. We then provide a mixed integer linear programming formulation of the optimization problem., which however leads to unacceptably high complexity for networks of non-trivially small size. We then propose both greedy and metaheuristic approaches for the sub-optimal design of logical topologies with acceptable complexity. Finally, we derive lower bounds that allow the assessment of the performance of the proposed algorithms. Some numerical results indicate that the proposed metaheuristics largely outperform the greedy approaches, and are able to obtain very good logical topologies.