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
Author: Cavalcante, VF
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
Subject: Lagrangian relaxation
cutting planes
Integer Programming
vertex separator
Country: EUA
Editor: Wiley-blackwell
Citation: Networks. Wiley-blackwell, v. 57, n. 3, n. 212, n. 230, 2011.
Rights: fechado
Identifier DOI: 10.1002/net.20420
Date Issue: 2011
Appears in Collections:Unicamp - Artigos e Outros Documentos

Files in This Item:
File Description SizeFormat 
WOS000290359800003.pdf242.28 kBAdobe PDFView/Open

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