Computing Minimum Spanning Trees with Uncertainty

Michael Hoffmann, Thomas Erlebach, Danny Krizanc, Matús Mihal'áK & Rajeev Raman
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 a set $A_e$, called an uncertainty area, that contains the actual edge weight $w_e$ is known. The algorithm can `update' $e$ to obtain the edge weight $w_e in A_e$. The task is to output the edge set of a minimum spanning tree after a...