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

doi:10.15960/j.cnki.issn.1007-6093.2024.02.012

运筹学学报（中英文） ›› 2024, Vol. 28 ›› Issue (2): 151-158.doi: 10.15960/j.cnki.issn.1007-6093.2024.02.012

• • 上一篇

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

杨子兰¹^,², 朱娟萍²^,*(), 杨宇²

1. 丽江文化旅游学院信息学院, 云南丽江 674199
2. 云南大学数学与统计学院, 云南昆明 650091

收稿日期:2021-03-26 出版日期:2024-06-15 发布日期:2024-06-07
通讯作者: 朱娟萍 E-mail:jpzhu@ynu.edu.cn
基金资助:
国家自然科学基金(11126355);云南省教育厅科学基金(2022J1217);云南省地方本科高校基础研究联合专项资金(202301BA070001-092);丽江文化旅游学院校级中青年学术和技术后备人才(2023xshb10)

The expansion problem of maximum capacity spanning arborescence in networks

Zilan YANG¹^,², Juanping ZHU²^,*(), Yu YANG²

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:2021-03-26 Online:2024-06-15 Published:2024-06-07
Contact: Juanping ZHU E-mail:jpzhu@ynu.edu.cn

摘要/Abstract

摘要：

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

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

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

中图分类号:

O157.6

杨子兰, 朱娟萍, 杨宇. 有向网络中最大容量支撑树形图扩容问题[J]. 运筹学学报（中英文）, 2024, 28(2): 151-158.

Zilan YANG, Juanping ZHU, Yu YANG. The expansion problem of maximum capacity spanning arborescence in networks[J]. Operations Research Transactions, 2024, 28(2): 151-158.

图/表 1

参考文献 20

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. doi: 10.1016/j.trb.2020.12.002
9	张国清,程苏琦.小世界网络中的删边扩容效应[J].中国科学: 信息科学,2012,42(2):151-160.
10	赵焱鑫,李黎,王小明.复杂网络加边扩容策略研究[J].计算机应用研究,2015,32(6):1839-1841. doi: 10.3969/j.issn.1001-3695.2015.06.053
11	FulkersonD R.Increasing the capacity of a network: The parametric budget problem[J].Management Science,1959,5(4):472-483. doi: 10.1287/mnsc.5.4.472
12	SchwarzS,KrumkeS O.On budget—constrained flow improvement[J].Information Proccssing Letters,1998,66,291-297. doi: 10.1016/S0020-0190(98)00070-2
13	YangC,LiuJ L.A capacity expansion problem with budget constraint and bottleneck limitation[J].Acta Mathematica Scientia,2002,22(2):207-212. doi: 10.1016/S0252-9602(17)30473-3
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. doi: 10.1080/10556780290027819
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. doi: 10.1007/s10479-018-2862-7
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. doi: 10.6028/jres.071B.032

[1]	苏兵, WyattCarlson, 范佳彬, GAO Arthur, 邵艳君, 林国辉. 最小化碳排放的共享单车迁移问题[J]. 运筹学学报, 2022, 26(3): 75-91.
[2]	张斌武, 关秀翠. 单位无穷范数下边权有界的最小支撑树逆最优值问题[J]. 运筹学学报, 2022, 26(3): 44-56.
[3]	陆书翔, 吕长虹, 秦涛. 集装箱码头桥机调度问题基于完工时间下界的算法[J]. 运筹学学报, 2020, 24(3): 67-76.
[4]	仲维亚, 杨若瑶. 工件具有子工件工期的排序问题[J]. 运筹学学报, 2019, 23(2): 67-74.
[5]	蔡爽, 杨珂, 刘克. 具有机器适用限制的分布式置换流水车间问题的模型与算法[J]. 运筹学学报, 2018, 22(4): 17-30.
[6]	张龙. 储存时间有上限的两阶段供应链排序问题[J]. 运筹学学报, 2017, 21(2): 126-134.
[7]	梁作松. 线图上的团染色问题[J]. 运筹学学报, 2016, 20(3): 92-98.
[8]	林浩, 林澜. 网络最小覆盖流问题[J]. 运筹学学报, 2014, 18(4): 96-104.
[9]	徐健腾, 张玉忠, 柏庆国. 多供应商多零售商下经济批量问题的多项式时间算法研究[J]. 运筹学学报, 2011, 15(4): 102-114.

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

The expansion problem of maximum capacity spanning arborescence in networks

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 1

参考文献 20

相关文章 9

编辑推荐

Metrics

本文评价