有向网络中最大容量支撑树形图扩容问题  

The expansion problem of maximum capacity spanning arborescence in networks

作　　者：杨子兰 朱娟萍[2] 杨宇 Zilan YANG;Juanping ZHU;Yu YANG(Department of Information,Lijiang Culture and Tourism College,Lijiang 674199,Yunnan,China;School of Mathematics and Statistics,Yunnan University,Kunming 650091,Yunnan,China)

机构地区：[1]丽江文化旅游学院信息学院,云南丽江674199 [2]云南大学数学与统计学院,云南昆明650091

出　　处：《运筹学学报（中英文）》2024年第2期151-158,共8页Operations Research Transactions

基　　金：国家自然科学基金(No.11126355);云南省教育厅科学基金(No.2022J1217);云南省地方本科高校基础研究联合专项资金(No.202301BA070001-092);丽江文化旅游学院校级中青年学术和技术后备人才(No.2023xshb10)。

摘　　要：针对有向网络中最大容量支撑树形图扩容问题(EMCSA),由0-1背包问题出发归约出EMCSA问题的一个实例,从而证明EMCSA问题是NP-困难的,并且给出解决EMCSA问题的一个启发式算法。最后,考虑EMCSA问题的一种特殊情况:有向网络中最大容量支撑树形图的最少弧扩容问题(NEMCSA),采用权重差最小换弧方法设计时间复杂度为O(mn)的多项式时间算法。For the expansion problem of the maximum capacity spanning arborescence in networks(EMCSA),NP-hardness is proved by constructing an instance of EMCSA from 0-1 knapsack problem,and a heuristic algorithm is designed.Finally,one special version of EMCSA,the expansion problem of the minimum arc number on the maximum capacity spanning arborescence in networks(NEMCSA),is considered.For NEMCSA,a strongly polynomial algorithm,in O(mn)time,is provided by substituting the arc with the minimum weight difference.

关 键 词：最大容量树形图 扩容 NP-困难 启发式算法 多项式时间算法 

分 类 号：O157.6[理学—数学]