General Variable Neighborhood Search for computing graph separators |
| |
Authors: | Jesús Sánchez-Oro Nenad Mladenović Abraham Duarte |
| |
Affiliation: | 1.Dpto. de Ciencias de la Computación,Universidad Rey Juan Carlos,Móstoles,Spain;2.LAMIH, Université de Valenciennes,Valenciennes,France |
| |
Abstract: | 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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|