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

arXiv (Cornell University)

Abstract

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.

Authors 2

1. Corinna Mathwieser Aachen

   RWTH Aachen University · Graz University of Technology

   Affiliation as printed

   Eranda Çela TU Graz , Austria

   RWTH Aachen University , Germany

2. Eranda Çela