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

A clone is a set of functions that is closed under generalized substitution.
The set FP of functions being computable deterministically in polynomial
time is such a clone. It is well-known that the set of subclones of every
clone forms a lattice. We study the lattice below FP, which ... more >>>

The PPSZ algorithm presented by Paturi, Pudlak, Saks, and Zane in 1998 has the nice feature that the only satisfying solution of a uniquely satisfiable $3$-SAT formulas can be found in expected running time at most $\Oc(1.3071^n).$ Using the technique of limited independence, we can derandomize this algorithm yielding $\Oc(1.3071^n)$ ... more >>>