General Variable Neighborhood Search for computing graph separators

Computing graph separators in networks has a wide range of real‐world applications. For instance, in telecommunication networks, a separator determines the capacity and brittleness of the network. In the field of graph algorithms, the computation of balanced small‐sized separators is very useful, especially for divide‐and‐conquer algorithms. In bioinformatics and computational biology, separators are required in grid graphs providing a simplified representation of proteins. This papers presents a new heuristic algorithm based on the Variable Neighborhood Search methodology for computing vertex separators. We compare our procedure with the state‐of‐the‐art methods. Computational results show that our procedure obtains the optimum solution in all of the small and medium instances, and high‐quality results in large instances.