000169406 001__ 169406 000169406 005__ 20260225153354.0 000169406 0247_ $$2doi$$a10.1016/j.procs.2025.10.289 000169406 0248_ $$2sideral$$a148322 000169406 037__ $$aART-2025-148322 000169406 041__ $$aeng 000169406 100__ $$0(orcid)0009-0003-6686-0505$$aAnglada, Sergio$$uUniversidad de Zaragoza 000169406 245__ $$aGeneralized Capacitated Vertex Separator Problem: Models and Algorithms 000169406 260__ $$c2025 000169406 5060_ $$aAccess copy available to the general public$$fUnrestricted 000169406 5203_ $$aGiven 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. 000169406 536__ $$9info:eu-repo/grantAgreement/ES/AEI/PCI2024-155092-2$$9info:eu-repo/grantAgreement/ES/AEI/PID2023-148599NB-I00$$9info:eu-repo/grantAgreement/ES/DGA/E41-23R$$9info:eu-repo/grantAgreement/ES/MICINN/PID2022-139543OB-C43 000169406 540__ $$9info:eu-repo/semantics/openAccess$$aby-nc-nd$$uhttps://creativecommons.org/licenses/by-nc-nd/4.0/deed.es 000169406 655_4 $$ainfo:eu-repo/semantics/article$$vinfo:eu-repo/semantics/publishedVersion 000169406 700__ $$0(orcid)0000-0002-5630-3719$$aGalé, Carmen$$uUniversidad de Zaragoza 000169406 700__ $$aSalazar-González, Juan José 000169406 7102_ $$12007$$2265$$aUniversidad de Zaragoza$$bDpto. Métodos Estadísticos$$cÁrea Estadís. Investig. Opera. 000169406 773__ $$g273 (2025), 125-132$$tProcedia computer science$$x1877-0509 000169406 8564_ $$s366068$$uhttps://zaguan.unizar.es/record/169406/files/texto_completo.pdf$$yVersión publicada 000169406 8564_ $$s2081539$$uhttps://zaguan.unizar.es/record/169406/files/texto_completo.jpg?subformat=icon$$xicon$$yVersión publicada 000169406 909CO $$ooai:zaguan.unizar.es:169406$$particulos$$pdriver 000169406 951__ $$a2026-02-25-14:58:46 000169406 980__ $$aARTICLE