Partitioning a Graph Constraining the Weight of its Cuts

We consider the problem of partitioning a graph into multiple components when the capacity of cut-edges is restricted. The objective function can be formulated in several ways. The different problems studied are: Maximizing Parallelism (MP), Most Uniform Partition (MUP) and also p-Most Uniform Partition (p-MUP). We provide an integer programming model, an exact combinatorial algorithm and a heuristic approach. Finally, an extensive computational experience and a comparative analysis between the different methods and considered problems is reported