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

作     者：杨子兰 朱娟萍 杨宇 Zilan YANG;Juanping ZHU;Yu YANG

作者机构：丽江文化旅游学院信息学院云南丽江674199 云南大学数学与统计学院云南昆明650091 

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

出 版 物：《运筹学学报（中英文）》 (Operations Research Transactions)

年 卷 期：2024年第28卷第2期

页      码：151-158页

摘      要：针对有向网络中最大容量支撑树形图扩容问题(EMCSA),由0-1背包问题出发归约出EMCSA问题的一个实例,从而证明EMCSA问题是NP-困难的,并且给出解决EMCSA问题的一个启发式算法。最后,考虑EMCSA问题的一种特殊情况:有向网络中最大容量支撑树形图的最少弧扩容问题(NEMCSA),采用权重差最小换弧方法设计时间复杂度为O(mn)的多项式时间算法。

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

学科分类：07[理学] 070104[070104] 0701[理学-数学类] 

核心收录：

D　O　I：10.15960/j.cnki.issn.1007-6093.2024.02.012

馆 藏 号：203128257...