Authors: Sánchez-Oro, Jesús
Mladenović, Nenad 
Duarte, Abraham
Title: General Variable Neighborhood Search for computing graph separators
Journal: Optimization Letters
Volume: 11
Issue: 6
First page: 1069
Last page: 1089
Issue Date: 1-Aug-2017
Rank: M21
ISSN: 18624472
DOI: 10.1007/s11590-014-0793-z
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: Combinatorial optimization | Graph separators | Metaheuristics | VNS
Publisher: Springer Link

Show full item record


checked on May 19, 2024

Page view(s)

checked on May 9, 2024

Google ScholarTM




Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.