All reports by Author Marco Laumanns:

__
TR05-029
| 2nd March 2005
__

Frank Neumann, Marco Laumanns#### Speeding Up Approximation Algorithms for NP-hard Spanning Forest Problems by Multi-objective Optimization

Revisions: 1

Frank Neumann, Marco Laumanns

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

more >>>