English

运筹学学报 >

2024 , Vol. 28 >Issue 2: 151 - 158

DOI: https://doi.org/10.15960/j.cnki.issn.1007-6093.2024.02.012

 

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

展开
  • 1. 丽江文化旅游学院信息学院, 云南丽江 674199
    2. 云南大学数学与统计学院, 云南昆明 650091
朱娟萍   E-mail: jpzhu@ynu.edu.cn

收稿日期: 2021-03-26

  网络出版日期: 2024-06-07

基金资助

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

版权

运筹学学报编辑部, 2024, 版权所有，未经授权。
收起

The expansion problem of maximum capacity spanning arborescence in networks

Expand
  • 1. Department of Information, Lijiang Culture and Tourism College, Lijiang 674199, Yunnan, China
    2. School of Mathematics and Statistics, Yunnan University, Kunming 650091, Yunnan, China

Received date: 2021-03-26

  Online published: 2024-06-07

Copyright

, 2024, All rights reserved, without authorization
Fold

摘要

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

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

本文引用格式

杨子兰, 朱娟萍, 杨宇 . 有向网络中最大容量支撑树形图扩容问题[J]. 运筹学学报, 2024 , 28(2) : 151 -158 . DOI: 10.15960/j.cnki.issn.1007-6093.2024.02.012

Abstract

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.

Key words： maximum capacity arborescence; capacity expansion; NP-hard; heuristic algorithm; polynomial time algorithm

参考文献

1 黄韬,霍如,刘江,等.未来网络发展趋势与展望[J].中国科学: 信息科学,2019,49,941-948.
2 张超. 有向网络容量扩张问题研究[D]. 武汉: 华中科技大学, 2007.
3 LiJ P,ZhuJ P.The capacity expansion path problem in networks[J].Journal of Applied Mathematics,2013,7(16):361-376.
4 杨宇. 有向网络中最大容量树形图扩容问题[D]. 昆明: 云南大学, 2011.
5 朱娟萍. 限制性网络扩容问题[D]. 昆明: 云南大学, 2011.
6 李彬,张洁,陈宋宋,等.基于复杂网络的电力通信网扩容保护策略[J].电网技术,2018,42(6):1974-1980.
7 王凌风,卢国潇.基于帕累托法则的网络负荷扩容研究[J].邮电设计技术,2019,7,54-59.
8 FragkosL,CordeauJ F,JansR.Decomposition methods for large-scale network expansion problems[J].Transportation Research Part B,2021,144,60-80.
9 张国清,程苏琦.小世界网络中的删边扩容效应[J].中国科学: 信息科学,2012,42(2):151-160.
10 赵焱鑫,李黎,王小明.复杂网络加边扩容策略研究[J].计算机应用研究,2015,32(6):1839-1841.
11 FulkersonD R.Increasing the capacity of a network: The parametric budget problem[J].Management Science,1959,5(4):472-483.
12 SchwarzS,KrumkeS O.On budget—constrained flow improvement[J].Information Proccssing Letters,1998,66,291-297.
13 YangC,LiuJ L.A capacity expansion problem with budget constraint and bottleneck limitation[J].Acta Mathematica Scientia,2002,22(2):207-212.
14 ZhangJ Z,YangC,LinY X.A class of bottleneck expansion problems[J].Computers & Operations Research,2001,28(6):505-519.
15 ZhangJ Z,LiuJ L.An oracle strongly polynomial algorithm for bottleneck expansion problems[J].Operation Methods and Software,2002,17(1):61-75.
16 YangC,ZhangJ Z.On the bottleneck capacity expansion problems on networks[J].Acta Mathematica Scientia,2006,26B(2):202-208.
17 TaghaviM,HuangK.A Lagrangian relaxation approach for stochastic network capacity expansion with budget constraints[J].Annals of Operations Research,2020,284,605-621.
18 田丰,马仲蕃.图与网络流理论[M].北京:科学出版社,1987.
19 ChuY J,LiuT H.On the shortest arborescence of a directed graph[J].Science Sinica,1965,14,1396-1400.
20 EdmondsJ.Optimum branchings[J].Research of the National Bureau of Standards,1967,71B,233-240.
Options
文章导航

/

〈 〉