Degree-constrained minimum spanning tree problem with uncertain edge weights |
| |
| Affiliation: | 1. Anhui Province Key Laboratory of Software Engineering in Computing and Communication, School of Computer Science and Technology, University of Science and Technology of China, Hefei 230027, Anhui, China;2. School of Computer & Communication Engineering, University of Science & Technology, Beijing, China;1. College of Physics and Information Engineering, Minnan Normal University, Zhangzhou 363000, PR China;2. National Laboratory of Industrial Control Technology, Institute of Cyber-Systems and Control, Zhejiang University, Hangzhou 310027, PR China;1. Department of Computer Science and Technology, School of Computer and Communication Engineering, University of Science and Technology Beijing, 100083 Beijing, China;2. Beijing Key Laboratory of Knowledge Engineering for Materials Science, University of Science and Technology Beijing, No. 30 Xueyuan Road, Haidian Zone 100083, China;1. Department of Information Technology, Camellia Institute of Technology, Madhyamgram, Kolkata 700129, India;2. Department of Information Technology, RCC Institute of Information Technology, Beliaghata, Kolkata 700015, India;3. Department of Computer Science & Engineering, Jadavpur University, Kolkata 700032, India |
| |
| Abstract: | 
Uncertainty theory has shown great advantages in solving many nondeterministic problems, one of which is the degree-constrained minimum spanning tree (DCMST) problem in uncertain networks. Based on different criteria for ranking uncertain variables, three types of DCMST models are proposed here: uncertain expected value DCMST model, uncertain α-DCMST model and uncertain most chance DCMST model. In this paper, we give their uncertainty distributions and fully characterize uncertain expected value DCMST and uncertain α-DCMST in uncertain networks. We also discover an equivalence relation between the uncertain α-DCMST of an uncertain network and the DCMST of the corresponding deterministic network. Finally, a related genetic algorithm is proposed here to solve the three models, and some numerical examples are provided to illustrate its effectiveness. |
| |
| Keywords: | Degree-constrained minimum spanning tree Uncertainty theory Genetic algorithm |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
