Connected Balanced Graph Partitions

Abstract

Technological advances have contributed to an increasingly connected society, providing an improvement in the quality of life in the most diverse aspects. To deal with problems such as, for example, about sets of objects that exhibit properties that translate into binary relations between them, and in which the objective is to discover the existence of certain substructures and / or to optimize some function, especially those of a discrete nature, the Graphs can be the appropriate mathematical structures. Problems with balanced partitions can be applied in this context, in the sense that the input graph can have weights associated with its vertices and the balance must take into account the weight of the connected subgraphs of the partition. When needing this concept of balance, we obtain some variants of the problem. Therefore, the focus of this article is a problem of this nature, which we call the Balanced Connected Partition Problem (PCB). Throughout the study, the computational experiments conducted showed that the exact algorithms implemented performed substantially better than the exact methods published in the literature. Additionally, we obtained the first polyhedral results associated with the second formulation restricted to the case of uniform weights. Such results can lead to new approaches to the PCBk.