Degree-constrained minimum spanning tree problem of uncertain random network

A degree-constrained minimum spanning tree (DCMST) problem involving any network aims to find the least weighted spanning tree of that network, subject to constraints on node degrees. In this paper, we first define a DCMST problem in an uncertain random network, where some weights are uncertain variables and others are random variables. We also introduce the concept of an ideal chance distribution for DCMST problem. In order to seek out the degree-constrained spanning tree (DCST) closest to the ideal chance distribution, an uncertain random programming model is formulated. An algorithm is presented to solve the DCMST problem. The effectiveness of our method and algorithm are exhibited by solving a numerical example.