Special Cases of the Minimum Spanning Tree Problem under Explorable Edge and Vertex Uncertainty

11/28/2022
by   Corinna Mathwieser, et al.
0

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.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset