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
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: Combinatorial optimization | Graph separators | Metaheuristics | VNS
Publisher: Springer Link

Show full item record

SCOPUSTM   
Citations

12
checked on Dec 5, 2021

Page view(s)

11
checked on Dec 6, 2021

Google ScholarTM

Check

Altmetric

Altmetric


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