We give faster approximation algorithms for the
generalization of two NP-hard spanning tree problems. First,
we investigate the problem of minimizing the degree of
minimum spanning forests. Fischer \cite{FISCH93}
has shown how to compute a minimum spanning tree of degree
at most $b \cdot \Delta^* + \lceil \log_b n \rceil$ in time
$O(n^{4 + 1/ \ln b})$ for any $b>1$, where $\Delta^*$ is the value of
an optimal solution. We model our generalization as a multi-objective optimization problem and give a deterministic algorithm that computes for each number of connected components a solution with the same
approximation quality as the algorithm of Fischer and runs
in time $O(n^{3 + 1/ \ln b})$. After that, we take a
multi-objective view on the problem of computing minimum
spanning trees with nonuniform degree bounds, which has been
examined by K{\"o}nemann and Ravi \cite{KOE03}. Given degree
bounds $B_v$ for each vertex $v \in V$, we construct an
algorithm that computes for each number of connected
components a spanning forest in which each vertex $v$ has
degree $O(B_v + \log n)$ and whose weight is at most a constant times the weight of a minimum spanning forest obeying the degree bounds. The total runtime of our algorithm is $O(n^{3 + 2 / \ln b})$ for an arbitrary constant $b>1$. Setting $b=e^k$, $k > 2/3$ an arbitrary constant, the runtime is by a factor $n^{3- 2/k} \log n$ less than the given bound by K{\"o}nemann and Ravi.

We give faster approximation algorithms for the
generalization of two NP-hard spanning tree problems. First,
we investigate the problem of minimizing the degree of
minimum spanning forests. The task is to compute for each
number of connected components a minimum spanning forest
whose degree is as small as possible. Fischer
has shown how to compute a minimum spanning tree of degree
at most $b \cdot \Delta^* + \lceil \log_b n \rceil$ in time
$O(n^{4 + 1/ \ln b})$ for any $b>1$, where $\Delta^*$ is the value of
an optimal solution. We model our
generalization as a multi-objective optimization problem and
give a deterministic algorithm that computes for each number
of connected components a solution with the same
approximation quality as the algorithm of Fischer and runs
in time $O(n^{3 + 1/ \ln b})$. After that, we take a
multi-objective view on the problem of computing minimum
spanning trees with nonuniform degree bounds, which has been
examined by K{\"o}nemann and Ravi. Given degree
bounds $B_v$ for each vertex $v \in V$, we construct an
algorithm that computes for each number of connected
components a spanning forest in which each vertex $v$ has
degree $O(B_v + \log n)$ and whose weight is at most a
constant times the weight of a minimum spanning forest
obeying the degree bounds. The total runtime of our
algorithm is $O(n^5)$, which is by a factor of $n \log n$
less than the algorithm of K{\"o}nemann and Ravi.