Before revision: Partitioning problems where the goal is to partition a graph into connected components are known to be NP-hard for some graph classes but polynomial-time solvable for others. We consider different variants of the (l,u)-partition problem: the p-(l,u)-partition problem and the minimum resp. maximum (l,u)-partition problem. That is partitioning a graph into exactly p or a minimal resp. maximal number of clusters such that every cluster fulfills the following weight condition: the weight of each cluster should to be at least l and at most u.
After revision: Partitioning problems where the goal is to partition a graph into connected components such that each component fulfills upper and lower weight constraints. Partitioning into a minimum, maximum or a fixed number of clusters such that every cluster fulfills the following weight condition: the weight of each cluster should to be at least l and at most u.