Special cases of the minimum spanning tree problem under explorable edge and vertex uncertainty

Networks, vol. 83, pp. 587–604

Abstract

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 corresponding Aachen Lehr‐ und Forschungsgebiet Kombinatorische Optimierung

   RWTH Aachen University

   Affiliation as printed

   Lehr‐ und Forschungsgebiet Kombinatorische Optimierung RWTH Aachen University Aachen Germany

   Lehr- und Forschungsgebiet Kombinatorische Optimierung, RWTH Aachen University, Aachen, Germany

2. Eranda Çela

   Graz University of Technology

   Affiliation as printed

   Department of Discrete Mathematics TU Graz Graz Austria

   Department of Discrete Mathematics, TU Graz, Graz, Austria