Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

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

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 >>>

ISSN 1433-8092 | Imprint