Please use this identifier to cite or link to this item:
|Type:||Artigo de periódico|
|Title:||Exact Algorithms for the Vertex Separator Problem in Graphs|
de Souza, CC
|Abstract:||In this article, we propose a Lagrangian relaxation framework to solve the vertex separator problem (VSP). This framework is based on the development of relax-and-cut algorithms which embed the separation of valid inequalities for the VSP discussed by Bales and de Souza (Math Program 103 (2005), 583-608) in the subgradient method. These relax-and-cut algorithms are then used as a preprocessing phase in a hybrid algorithm which combines them with branch-and-cut algorithms proposed by de Souza and Bales (Math Program 103 (2005), 609-631). This is done basically by feeding the branch-and-cut algorithms not only with the primal bound but also the cuts separated during the preprocessing phase. Computational results obtained with benchmarks from the literature showed that the hybrid algorithm developed here outperforms the best exact algorithm available for the VSP to date. (C) 2011 Wiley Periodicals, Inc. NETWORKS, Vol. 57(3), 212-230 2011|
|Appears in Collections:||Unicamp - Artigos e Outros Documentos|
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.