A Model and Algorithm for Minimum Spanning Tree Problems in Uncertain Networks

This paper considers the problem of minimum spanning trees in uncertain networks in which the edge weights are random variables. We propose the concept of expected minimum spanning tree and formulate the model according to expected value. In order to solve the model, a hybrid intelligent algorithm combined genetic algorithm and stochastic simulation is given, and the Prufer encoding schemes represented spanning trees are adopted. The algorithm has been proved to be useful for solving practical problems by a numerical example.