Uncertain Distribution-Minimum Spanning Tree Problem

This paper studies the minimum spanning tree problem on a graph with uncertain edge weights, which are formulated as uncertain variables. The concept of ideal uncertain minimum spanning tree (ideal UMST) is initiated by extending the definition of the uncertain α-minimum spanning tree to reect the overall properties of the α-minimum spanning tree weights at any confidence level α∈[0,1]. On the basis of this new concept, the definition of uncertain distribution-minimum spanning tree is proposed in three ways. Particularly, by considering the tail value at risk from the perspective of risk management, the notion of uncertain β-distribution-minimum spanning tree (β-distribution-UMST) is suggested. It is shown that the β-distribution-UMST is just the uncertain expected minimum spanning tree when β = 0. For any β∈[0,1], this problem can be effectively solved via the proposed deterministic graph transformation-based approach with the aid of the β-distribution-path optimality condition. Furthermore, the proposed definitions and solutions are illustrated by some numerical examples.