Show simple item record

Variable Neighborhood Search for the Vertex Separation Problem

dc.contributor.authorDuarte, Abraham
dc.contributor.authorEscudero, Laureano F.
dc.contributor.authorMartí, Rafael
dc.contributor.authorMladenovic, Nenad
dc.contributor.authorPantrigo, Juan José
dc.contributor.authorSánchez-Oro, Jesús
dc.identifier.citationVariable neighborhood search for the vertex separation problem Duarte A., Escudero L.F., Marti R., Mladenovic N., Pantrigo J.J., Sanchez-Oro J. (2012) Computers and Operations Research, 39 (12) , pp. 3247-3255.
dc.description.abstractThe vertex separation problem belongs to a family of optimization problems in which the objective is to nd the best separator of vertices or edges in a generic graph. This optimization problem is strongly related to other well-known graph problems; such as the Path-Width, the Node Search Number or the Interval Thickness, among others. All of these optimization problems are NP-hard and have practical applications in VLSI, computer language compiler design or graph drawing. Up to know, they have been generally tackled with exact approaches, presenting polynomial-time algorithms to obtain the optimal solution for speci c types of graphs. However, in spite of their practical applications, these problems have been ignored from a heuristic perspective, as far as we know. In this paper we propose a pure 0-1 optimization model and a metaheuristic algorithm based on the variable neighborhood search methodology for the vertex separation problem on general graphs. Computational results show that small instances can be optimally solved with this optimization model and the proposed metaheuristic is able to nd high-quality solutions with a moderate computing time for large-scale
dc.rightsAtribución-NoComercial-SinDerivadas 3.0 España*
dc.subjectEstadística y Demografíaes
dc.subjectCombinatorial Optimizationes
dc.subjectVariable Neigborhood Searches
dc.subjectLayout Problemses
dc.titleVariable Neighborhood Search for the Vertex Separation Problemes
dc.subject.unesco1203.17 Informáticaes
dc.subject.unesco52 Demografíaes
dc.subject.unesco5207.10 Estadísticas de Poblacioneses
dc.description.departamentoCiencias de la Computación

Files in this item

This item appears in the following Collection(s)

Show simple item record

Atribución-NoComercial-SinDerivadas 3.0 EspañaExcept where otherwise noted, this item's license is described as Atribución-NoComercial-SinDerivadas 3.0 España