摘要
针对有向网络中最大容量支撑树形图扩容问题(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.
作者
杨子兰
朱娟萍
杨宇
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)
出处
《运筹学学报（中英文）》
CSCD
北大核心
2024年第2期151-158,共8页
Operations Research Transactions
基金
国家自然科学基金(No.11126355)
云南省教育厅科学基金(No.2022J1217)
云南省地方本科高校基础研究联合专项资金(No.202301BA070001-092)
丽江文化旅游学院校级中青年学术和技术后备人才(No.2023xshb10)。
关键词
最大容量树形图
扩容
NP-困难
启发式算法
多项式时间算法
maximum capacity arborescence
capacity expansion
NP-hard
heuristic algorithm
polynomial time algorithm
