限制性支撑树最大容量扩张问题

大理大学学报 ›› 2023, Vol. 8 ›› Issue (12): 10-14.

限制性支撑树最大容量扩张问题

（1. 丽江文化旅游学院信息学院，云南丽江 674199； 2. 昭通学院数学与统计学院，云南昭通 657000）

收稿日期:2023-02-28 出版日期:2023-12-15 发布日期:2024-01-07
通讯作者: 李睿，副教授，E-mail： 47640481@qq.com。
作者简介:杨子兰，副教授，主要从事组合最优化研究。
基金资助:
国家自然科学基金项目（11126355）；云南省教育厅科学研究基金项目（2017ZDX270；2022J1217）；云南省地方本科高校基础研究联合专项资金项目（202301ＢＡ070001-092）

The Maximum Capacity Expansion of Spanning Tree Problem with Constraints

（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）是 NP-难问题。针对 MCESTC 问题，采用允许增加支撑树长度值的双边替换策略设计了一个启发式算法进行求解，并证明了算法的正确性。最后，用实例阐述运用该算法求解问题的过程，从而验证算法的有效性。

关键词: 通信网络, 支撑树, 树边替换, 双边替换, 完美匹配

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

中图分类号:

O157.6

杨子兰 , 杨惠娟 , 李睿 . 限制性支撑树最大容量扩张问题[J]. 大理大学学报, 2023, 8(12): 10-14.

Yang Zilan, Yang Huijuan , Li Rui . The Maximum Capacity Expansion of Spanning Tree Problem with Constraints[J]. Journal of Dali University, 2023, 8(12): 10-14.