|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
checked on Dec 5, 2021
checked on Dec 6, 2021
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.