  Some experimental investigations have shown that evolutionary algorithms
(EAs) are efficient for the minimum label spanning tree (MLST) problem.
However, we know little about that in theory. As one step towards this issue,
we theoretically analyze the performances of the (1+1) EA, a simple version of
EAs, and a multi-objective evolutionary algorithm called GSEMO on the MLST
problem. We reveal that for the MLST$_{b}$ problem the (1+1) EA and GSEMO
achieve a $\frac{b+1}{2}$-approximation ratio in expected polynomial times of
$n$ the number of nodes and $k$ the number of labels. We also show that GSEMO
achieves a $(2ln(n))$-approximation ratio for the MLST problem in expected
polynomial time of $n$ and $k$. At the same time, we show that the (1+1) EA and
GSEMO outperform local search algorithms on three instances of the MLST
problem. We also construct an instance on which GSEMO outperforms the (1+1) EA.
