Generalized Capacitated Vertex Separator Problem: Models and Algorithms

Anglada, Sergio (Universidad de Zaragoza) ; Galé, Carmen (Universidad de Zaragoza) ; Salazar-González, Juan José

Resumen: 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.

Idioma: Inglés

DOI: 10.1016/j.procs.2025.10.289

Año: 2025

Publicado en: Procedia computer science 273 (2025), 125-132
ISSN: 1877-0509

Financiación: info:eu-repo/grantAgreement/ES/AEI/PCI2024-155092-2
Financiación: info:eu-repo/grantAgreement/ES/AEI/PID2023-148599NB-I00
Financiación: info:eu-repo/grantAgreement/ES/DGA/E41-23R
Financiación: info:eu-repo/grantAgreement/ES/MICINN/PID2022-139543OB-C43

Tipo y forma: Article (Published version)

Área (Departamento): Área Estadís. Investig. Opera. (Dpto. Métodos Estadísticos)