Computing Minimum Spanning Trees with Uncertainty

Thomas Erlebach, Michael Hoffmann, Danny Krizanc +2

We consider the minimum spanning tree problem in a setting where information about the edge weights of the given graph is uncertain. Initially, for each edge $e$ of the graph only…