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. These kind of partitioning problems are NP-hard for series-parallel graphs but can be solved in polynomial time on trees. In this paper we present partitioning algorithms for cactus graphs to show that these partition problems are polynomial-time solvable for this graph class as well .
We study the problem of partitioning a weighted 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 is NP-hard in general but polynomial-time solvable on trees. In this paper , we present a polynomial-time algorithm for cactus graphs . For other optimization goals or additional constraints, the partition problem becomes NP-hard even on trees and for a lower weight bound equal to zero. We show that our method can be used as an algorithmic framework to solve other partition problems for cactus graphs in pseudo-polynomial time .
R
Partitioning problems where the goal is to partition a
We study the problem of partitioning a weighted
R
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
such that each component fulfills upper and lower weight constraints. Partitioning into a minimum, maximum or a fixed
R
such that every cluster fulfills the following weight condition: the weight of each cluster should to be at least l and at most u. These kind of partitioning problems are
is
R
for series-parallel graphs but can be solved in polynomial time
in general but polynomial-time solvable
R
we present partitioning algorithms
, we present a polynomial-time algorithm
R
to show that these partition problems are polynomial-time solvable for this graph class as well
. For other optimization goals or additional constraints, the partition problem becomes NP-hard even on trees and for a lower weight bound equal to zero. We show that our method can be used as an algorithmic framework to solve other partition problems for cactus graphs in pseudo-polynomial time