Journal of Dali University ›› 2023, Vol. 8 ›› Issue (12): 10-14.

Previous Articles     Next Articles

The Maximum Capacity Expansion of Spanning Tree Problem with Constraints

  

  1. (1. Department of Information, Lijiang Culture and Tourism College, Lijiang, Yunnan 674199, China; 2. School of Mathematics and Statistics, Zhaotong College, Zhaotong, Yunnan 657000,China)
  • Received:2023-02-28 Online:2023-12-15 Published:2024-01-07

Abstract: The maximum capacity expansion of spanning tree problem with constraints (MCESTC) is NP-hard. A heuristic algorithm is designed to solve it by allowing an increase in the length value of the spanning tree through bilateral substitution strategy, and the correctness of the algorithm is proved. Finally, an example is used to illustrate the process of applying the algorithm to solve the problem, thereby verifying the effectiveness of the algorithm. 

Key words: communication network; spanning tree; tree edge replacement; bilateral substitution; perfect matching 

CLC Number: