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

作者：杨子兰; 朱娟萍; 杨宇

来源：运筹学学报, 2022, 1-9.

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

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

• 单位
  云南大学旅游文化学院