  This article studies the Minimum Spanning Tree Problem under Explorable
Uncertainty as well as a related vertex uncertainty version of the problem. We
particularly consider special instance types, including cactus graphs, for
which we provide randomized algorithms. We introduce the problem of finding a
minimum weight spanning star under uncertainty for which we show that no
algorithm can achieve constant competitive ratio.
