Skip to Main content Skip to Navigation
Journal articles

General Variable Neighborhood Search for computing graph separators

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.
Document type :
Journal articles
Complete list of metadata

https://hal-uphf.archives-ouvertes.fr/hal-03401153
Contributor : Kathleen Torck Connect in order to contact the contributor
Submitted on : Monday, October 25, 2021 - 11:57:33 AM
Last modification on : Wednesday, November 3, 2021 - 5:24:21 AM

Identifiers

Collections

Citation

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

Share

Metrics

Record views

6