Path Optimality Conditions for Minimum Spanning Tree Problem with Uncertain Edge Weights

• DOI: 10.1142/s0218488515500038
• Publication Date: 2015-02-16T06:41:59Z
• Authors: Jian Zhou; Lu Chen; Ke Wang
• Keywords: 0209 industrial biotechnology; 0202 electrical engineering, electronic engineering, information engineering; 02 engineering and technology

This paper investigates the uncertain minimum spanning tree (UMST) problem where the edge weights are assumed to be uncertain variables. In order to propose effective solving methods for the UMST problem, path optimality conditions as well as some equivalent definitions for two commonly used types of UMST, namely, uncertain expected minimum spanning tree (expected UMST) and uncertain α-minimum spanning tree (α-UMST), are discussed. It is shown that both the expected UMST problem and the α-UMST problem can be transformed into an equivalent classical minimum spanning tree problem on a corresponding deterministic graph, which leads to effective algorithms with low computational complexity. Furthermore, the notion of uncertain most minimum spanning tree (most UMST) is initiated for an uncertain graph, and then the equivalent relationship between the α-UMST and the most UMST is proved. Numerical examples are presented as well for illustration.