General Variable Neighborhood Search for computing graph separators - Université Polytechnique des Hauts-de-France Accéder directement au contenu
Article Dans Une Revue Optimization Letters Année : 2017

General Variable Neighborhood Search for computing graph separators

Résumé

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.
Fichier non déposé

Dates et versions

hal-03401153 , version 1 (25-10-2021)

Identifiants

Citer

Jesús Sánchez-Oro, Nenad Mladenovic, Abraham Duarte. General Variable Neighborhood Search for computing graph separators. Optimization Letters, 2017, 11 (6), pp.1069-1089. ⟨10.1007/s11590-014-0793-z⟩. ⟨hal-03401153⟩
15 Consultations
0 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More