169406 20260225153354.0 doi 10.1016/j.procs.2025.10.289 sideral 148322 ART-2025-148322 eng Anglada, Sergio Universidad de Zaragoza (orcid)0009-0003-6686-0505 Generalized Capacitated Vertex Separator Problem: Models and Algorithms 2025 Given an undirected graph and two numbers q and b, the Capacitated Vertex Separation Problem (CVSP) looks for a vertex subset of minimum cardinality such that the connected components in the subgraph generated after the vertex removal can be packed into no more than q bins of cardinality at most b. This problem has been studied in graph theory, and most of the success in solving it is due to the hypothesis that the objective function minimizes the number of deleted vertices, that is, each node removal contributes identically to the objective function. In our work, this hypothesis is relaxed so each vertex has a cost and a weight, and the problem aims to minimize the total cost of the removed vertices while the total vertex weight in each bin is within the given capacity b, still limiting the number of bins to at most q. We introduce several mathematical formulations for the new problem, called the Generalized Capacitated Vertex Separator Problem (GCVSP), and analyze the performance of algorithms based on such formulations. Access copy available to the general public Unrestricted info:eu-repo/grantAgreement/ES/AEI/PCI2024-155092-2 info:eu-repo/grantAgreement/ES/AEI/PID2023-148599NB-I00 info:eu-repo/grantAgreement/ES/DGA/E41-23R info:eu-repo/grantAgreement/ES/MICINN/PID2022-139543OB-C43 info:eu-repo/semantics/openAccess by-nc-nd https://creativecommons.org/licenses/by-nc-nd/4.0/deed.es info:eu-repo/semantics/article info:eu-repo/semantics/publishedVersion Galé, Carmen Universidad de Zaragoza (orcid)0000-0002-5630-3719 Salazar-González, Juan José 2007 265 Universidad de Zaragoza Dpto. Métodos Estadísticos Área Estadís. Investig. Opera. 273 (2025), 125-132 Procedia computer science 1877-0509 366068 http://zaguan.unizar.es/record/169406/files/texto_completo.pdf Versión publicada 2081539 http://zaguan.unizar.es/record/169406/files/texto_completo.jpg?subformat=icon icon Versión publicada oai:zaguan.unizar.es:169406 articulos driver 2026-02-25-14:58:46 ARTICLE