Revision #1 Authors: Frank Neumann, Marco Laumanns

Accepted on: 15th June 2005 00:00

Downloads: 1283

Keywords:

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.

TR05-029 Authors: Frank Neumann, Marco Laumanns

Publication: 7th March 2005 13:34

Downloads: 1136

Keywords:

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.