摘要
限制性支撑树最大容量扩张问题(the maximum capacity expansion of spanning tree problem with constraints,MCESTC)是NP-难问题。针对MCESTC问题,采用允许增加支撑树长度值的双边替换策略设计了一个启发式算法进行求解,并证明了算法的正确性。最后,用实例阐述运用该算法求解问题的过程,从而验证算法的有效性。
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.
作者
杨子兰
杨惠娟
李睿
Yang Zilan;Yang Huijuan;Li Rui(Department of Information,Lijiang Culture and Tourism College,Lijiang,Yunnan 674199,China;School of Mathematics and Statistics,Zhaotong College,Zhaotong,Yunnan 657000,China)
出处
《大理大学学报》
2023年第12期10-14,共5页
Journal of Dali University
基金
国家自然科学基金项目(11126355)
云南省教育厅科学研究基金项目(2017ZDX270
2022J1217)
云南省地方本科高校基础研究联合专项资金项目(202301BA070001-092)。
关键词
通信网络
支撑树
树边替换
双边替换
完美匹配
communication network
spanning tree
tree edge replacement
bilateral substitution
perfect matching
