Métodos exactos para el problema de equiparticionamiento de grafos en componentes conexas.

Abstract

In the present work, the graph partitioning problem in connected components is studied. The problem consists of partitioning an undirected graph with cost on the edges into a fixed number of connected components, such that the number of nodes in each component differs by at most one unit and the total cost of the edges with end-nodes in the same subset of nodes that induces a component is minimized. Several integer linear programming models using different approaches (maximizing the edges in the cut or minimizing the edges in the connected components) are presented and the results are compared. Moreover, several families of valid inequalities associated to the polytope of these formulations are exposed, together with a Branch & Cut algorithm for the studied problem. Computational results based on simulated instances of different sizes and densities are reported. Finally, conclusions about the present work are presented.