  In this paper, we consider different constrained partition problems for
weighted trees and cactus graphs. We focus on the (l,u)-partition problem,
which is the problem of partitioning a weighted graph into connected clusters
such that each cluster fulfills the lower and upper weight constraints l and u.
Partitioning into a minimum, maximum or a fixed number of clusters is known to
be NP-hard in general, but polynomial-time solvable on trees. We prove that
these three variants of the (l,u)-partition problem can be solved for cactus
graphs as well by presenting a polynomial-time algorithm. Additionally, we
present an efficient method to compute the corresponding partitions. 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 weighted trees and cactus graphs with a pseudopolynomial
runtime.
