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