randomnetwork.PDF

J Ambient Intell Human Comput DOI 10.1007/s12652-017-0493-5 ORIGINAL RESEARCH Degree‑constrained minimum spanning tree problem of uncertain random network 1 2 3 Xin Gao  · Lifen Jia  · Samarjit Kar   Received: 7 February 2017 / Accepted: 12 April 2017 © Springer-Verlag Berlin Heidelberg 2017 Abstract A degree-constrained minimum spanning tree 1 Introduction (DCMST) problem involving any network aims to ind the least weighted spanning tree of that network, subject to The minimum spanning tree (MST) problem, aiming to constraints on node degrees. In this paper, we irst deine ind the least weight in a deterministic network, was irst a DCMST problem in an uncertain random network, where introduced by Borüvka ( 1926). Extending Borüvka’s work some weights are uncertain variables and others are ran- Narula and Ho ( 1980) aimed to ind the MST of a determin- dom variables. We also introduce the concept of an ideal istic network subject to certain constraints on each node. chance distribution for DCMST problem. In order to seek In a deterministic network, all the weights are crisp num- out the degree-constrained spanning tree (DCST) closest bers. In the past decades, the DCMST problem involving to the ideal chance distribution, an uncertain random pro- deterministic networks has drawn great interest research- gramming model is formulated. An algorithm is presented ers among the world over and it has been applied in many to solve the DCMST problem. The efectiveness of our ields such as transportation, communications and logistics, method and algorithm are exhibited by solving a numerical etc. Many eicient classical algorit